题解 P6040 【「ACOI2020」课后期末考试滑溜滑溜补习班】

· · 题解

单调队列优化DP的板子题吖，很适合萌新上手

20 分做法

假设 f[i] 表示杀老师解决完第 i 个学生累计花费的最小精力。显然对于 i=1 有 f[1]=a[1]。

对于其他的 i 号学生，我们假设杀老师是从第 j 号学生直接跳过来的，那么状态转移方程分为三项： f[j] 表示从之前的累计值，(i-j-1)\times d+k 是应对学生调侃和移动花费的精力，a[i] 是解决当前学生问题花费的精力。

f[i]=f[j]+(i-j-1)\times d+k+a[i]

当然 j 是有范围的，i-x\leq j<i。当 j=i-1 时，实际情况就是杀老师没有跳过任何学生，是解决了上一个学生问题直接移动过来的的。

对于每个 f[i]，只需要寻找最小的一个 j 使得 f[j]+(i-j-1)\times d 有最小值即可。最后输出 f[n] 即可。时间复杂度 O(n^2)。

100 分做法

只需要做一点点改动就可以拿到满分了（巨大的跨越）。

由状态转移方程知，可以影响 f[i] 大小的只有 f[j] 和他们的距离 (i-j-1)，因为 k+a[i] 是个定值。

对于一个学生 i，假设最优策略是从 j 号跳转到 i 号，再任取一个不是最优的学生 t。那么对于学生 i+1，从 j 跳转过来更优还是从 t 跳转过来更优呢？答案一定是 j。因为从 i 号位置改跳到 i+1 位置只需要多花精力 d，二者都如此。原来 j 更优，现在依然更优。

这意味着，我们对于每个 f]i] 向前寻找最优的 j 时，不需要遍历整个 [i-x,i-1]，只需要取出我们之前记录的最优的 j。这里的所有 j 就可以用一个单调队列来维护。

每次得到 f[i] 的流程就应该是

1.弹出单调队列的过期元素（j<i-x）
2.取出单调队列的第一个元素，得到 f[i]
3.将 (f[i],i) 打包放入单调队列中，并弹出

弹出的条件是什么呢？并不是简单的 f[j]\geq f[i] 才弹出。根据我们之前推出的性质，从 j 跳转到某一个点 x，和从 i 跳转到某一个点 x，从 j 跳转一定会多花一个定值，即 (i-j)\times d （注意这里一定不要-1）。所以弹出的条件就是 f[j]\geq f[i]+(i-j)\times d

附上核心代码，仅供参考

    deque<pair<LL,int> >q; //不开LL见祖宗

    if(x==1){     //杀老师不能跳过时，需特判
        for(int i=1;i<=n;++i)f[n]+=a[i];
        cout<<f[n]+k*(LL)(n-1);
        return 0;
    }
    f[1]=a[1];
    q.push_back(make_pair(f[1],1));  //预处理
    for(int i=2;i<=n;++i){
        while(!q.empty()){
            if(q.front().second<i-x)q.pop_front();
             else break;    //弹出过期元素
        }
        LL fx=q.front().first;int lx=q.front().second;
        f[i]=fx+k+d*(LL)(i-lx-1)+a[i];  //得到f[i]
        while(!q.empty()){
            LL fx=q.back().first;int lx=q.back().second;
            if(fx+d*(LL)(i-lx)>=f[i])q.pop_back();
             else break;   //弹出
        }
        q.push_back(make_pair(f[i],i));  //压入当前元素
    }
    cout<<f[n];