题解：P11791 [JOI 2017 Final] 准高速电车 / Semiexpress

· · 题解

约定：以下称快车为高速电车，中车为准高速电车，慢车为普通列车。

本人语文不好，读错了两次题：

小清新贪心题。

Observation 1：对于每个站，到达它的最优方式永远是先坐快车到前面离它最近的快车站，再坐中车到前面离它最近的中车站，再坐慢车。

Prove 1：因为 B\le C\le A 且换乘不需要时间。

Observation 2：每两个快车站间独立，即在 i 和 i+1 快车站间放置中车站，不会影响 i+1 和 i+2 间点的可达性。

Prove 2：根据 Observation 1，如果需要达到快车站 i+1 和 i+2 之间的点，最优策略是坐快车坐到 i+1，坐到 i 再坐中车慢车到 i+1 是不优的。

Observation 3：有一种贪心策略：对于每两个快车站间，从前往后放中车站，每次在第一个无法达到到的点处放置中车站，直到 放了还是无法达到 或 这两个快车站间已经放了 M-K 个位置 为止。

Prove 3：显然我们可以看作从前往后放中车站。设放了 k 个，若放在之前可达的位置，我们可以把它平移到不可达的位置，设平移了 x 步。我们多花了 Cx 分钟，多走了原本花 Ax 时间才能走的路程，肯定更优。若隔空放，隔空的部分不可达而却在坐中车上多花了时间，也是不赚的。

Observation 4：根据 Observation 3，现在我们的问题就是在每两个快车站之间放多少个中车站。我们转化为这么一个问题：设 v_{i,j} 为 i 和 i+1 之间放第 j 个中车站能新增多少个可达点。每个 v_i 可以取一个前缀，一共最多取 K-M 个，最大化取得的总和。

Prove 4：简单的转化，显然。

现在有一个简单的 O(MK^2) 背包，f_{i,j} 为前 i 段取了 j 个的最大值。转移枚举当前取的个数 k，这是简单的。

Observation 5：对于一个 i，现在的 v_{i,j} 不增。

Prove 5：距离快车站 i 越远，坐中车时间越长，可以预留给坐慢车的时间越短，坐慢车的距离越短，每次拓展的距离越短。

Observation 6：可以把取一个前缀的条件去掉。

Prove 6：根据 Observation 5，v_{i,j} 不增，不取前缀不会比取前缀优。

Observation 7：又可以转化为把 v_{i,j} 排成一行，取 K 个数使总和最大。

Prove 7：不同段之间并没有外加的限制。

现在可以直接排序后取前 K 个了。复杂度 O(MK\log MK)。如果用优先队列维护，动态把当前已经不在前 K 个的删去，复杂度 O(MK\log K)。

int n,m,k,a,b,c,as=-1,p[N]; ll t;
priority_queue<int,vi,greater<int>> q;
void QwQ() {
    n=rd(),m=rd(),k=rd()-m,a=rd(),b=rd(),c=rd(),t=rdll();
    for(int i=1;i<=m;i++) p[i]=rd();
    for(int i=1;i<=m;i++) {
        if(1ll*(p[i]-1)*b>t) break;
        if(i==m) {as++; break;}
        as+=min((ll)p[i+1]-p[i],(t-1ll*(p[i]-1)*b)/a+1); int ct=0;
        for(ll x=p[i]+(t-1ll*(p[i]-1)*b)/a+1,y=t-1ll*(p[i]-1)*b-(x-p[i])*c,nx;y>=0&&x<p[i+1];y-=(nx-x)*c,x=nx) {
            nx=min((ll)p[i+1],x+y/a+1),q.push(nx-x);
            if(++ct==k) break;
        }
        for(;q.size()>k;) q.pop();
    }
    for(;q.size();) as+=q.top(),q.pop();
    wr(as,"\n");
}