AcWing 1090.绿色通道

· · 个人记录

原题链接

题目解析

摘自《动态规划 · 二、数据结构优化DP · 单调队列优化》 。

可以看到，我们希望空的题尽可能的分散，然而我们好像无法从正面直接枚举得到答案（一种一种组合的列举显然是不可能的），那我们便可以换个思路从答案开始思考：
设最长的空题段长度为 k，那么显然方案满足这一点，且在最优安排下满足时间小于等于 t ，而空题段长度大于 k 时显然不满足最优（马老师会很生气）可以继续向 k 靠近，小于 k 时总时间会大于 t，不符合题意。
于是我们发现，以正确答案 k 为界，将一个 [0,N] 的区间分成了两半，一半为合法非最优，一半不合法。这启示我们使用二分，逼近正确答案 k 。

当二分的 k 固定下来，问题变成了“在一个数列空出若干个连续长度不超过 k 的数之后数列的和是否小于 t ”，我们显然很难从“紧接着”转移状态，即转移过程非链状，而是跳跃的，所以我们设状态 f[i] 表示在第 i 道题并不空第 i 题下所需的最少时间，那么为了保证空题段合法，那么状态转移方程为：

f[i]=\min\limits_{i-k-1\leq j<i}\{f[j]+w_i\}=\min\limits_{i-k-1\leq j<i}\{f[j]\}+w_i

废话不多说，这里主要把单调队列的用法细节详细讲解。输入不必多说，从二分开始。

首先，这个空的题目数量不应该为负数，所以左边界为 0 ；其次空的题目数量不可能超过总数 n 所以右边界为 n 。那么根据二分模板，为了防止二分死循环，我们需要在check()函数返回false时给l加一或给r减一。

成品如下：

    int l=0,r=n;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))  r=mid;
        else    l=mid+1;
    }

    printf("%d",l);
    return 0;

首先我们要搞清楚一件事，那就是对于f[i]来讲，他是由f[j]转移过来的并且j满足i-k-1<=j<i，所以单调队列存的是区间 [i-k-1,i-1] 的最小值，因为首先第 i 道题是要做的，此前可以空 k 道题，但是不能空 k+1 道题，做第 i-k-1 道题并空 k 道题是可以的，即上述区间。
那么我们在更新一个f[]时，就应当先把其前k+1 个f[]的最小值用单调队列求出来，并且，在一开始，f[2]该由谁转移过来呢？显然不一定是 f[1] ，所以在一开始还要垫一个 0 。
那么最后的答案呢？一定是 f[n] 吗？显然最后一道并不一定要做，所以答案应当为 \min\limits_{n-k\leq i\leq n}\{f[i]\} ，那么如果答案小于 t ，我们就可以尝试空更少的题。

成品如下：


bool check(int k){
    hh=0,tt=-1;
    q[++tt]=0;//先垫一个0
    f[1]=a[1];//f[1]无需多虑
    for(int i=2;i<=n;i++){
        while(hh<=tt && q[hh]<i-k-1)    hh++;//边界为i-k-1
        while(hh<=tt && f[q[tt]]>=f[i-1])   tt--;//升序单调队列
        q[++tt]=i-1;//队列中存下标
        f[i]=f[q[hh]]+a[i];
    }

    for(int i=n-k;i<=n;i++)
        if(f[i]<=t) return true;
    return false;
}

当然可以更简洁：

bool check(int k){
    hh=0,tt=0;
    for(int i=1;i<=n;i++){
        while(hh<=tt && q[hh]<i-k-1)    hh++;
        f[i]=f[q[hh]]+a[i];
        while(hh<=tt && f[q[tt]]>=f[i]) tt--;
        q[++tt]=i;
    }
    for(int i=n-k;i<=n;i++)
        if(f[i]<=t) return true;
    return false;
}