猫史档案馆

之前我讲过的动态规划包括树形dp、背包、状压dp和一些一般的线性dp。

我们可以利用决策区间的单调性、相邻决策在坐标系中的斜率的单调性以及决策单调性，这三个性质，来将复杂度优化一次或将其中一次优化为渐进 log 级别。

下面尝试通过2个例题来初探动态规划优化的巧妙方法。

 

 

单调队列优化

 

 

喵 dp

 

稍加思考可以发现，花费的金币越多，则跳跃距离的灵活度也更大。所以显然当金币增加时，最大得分不会更低，并且有可能增加。因此最大得分具有单调性（单调上升），显然二分判定 gg 。

然后思考 check 函数如何实现。

观察题目，发现每一个点都需要从它左边的点跳过来，并且它前面的点如何跳并不影响这个点之后的跳法。同时，一个点的最大得分，是从能跳到这个点的前面所有点中选取最优的一个。动态规划显然。

 

 · 状态表示： f(i) 表示以 i 结尾的所有跳跃路线获得的权值中的最大值。

 · 阶段划分：这一条跳跃的路线的结束位置（即 x[i]）。

 · 边界： f(0)=0

 

因此状态转移方程也就很明显了：

判定的时候，如果发现一个 f(i)​ 大于等于 k，直接返回 true，否则判定失败。

时间复杂度 O(n*n*log(n))。

//38 lines of AC_code
long long n,d,k,f[500005],a[500005][2];
bool check(int g)
{
    memset(f,-127,sizeof(f)); 
    long long x=max(d-g,(long long)1),s=d+g;
    f[0]=0;
    //外层循环枚举阶段i 
    for(long long i=1;i<=n;i++)
    {
        //内层循环对决策点j进行转移 
        for(long long j=i-1;j>=0;j--)
        {
            if(a[i][0]-a[j][0]<x)continue;
            if(a[i][0]-a[j][0]>s)break;
            //实行状态转移方程 
            f[i]=max(f[i],f[j]+a[i][1]);
            if(f[i]>=k)return true;
        }
    }
    return false;
}
int main()
{
    cin>>n>>d>>k;
    for(long long i=1;i<=n;i++)
        cin>>a[i][0]>>a[i][1];
    l=0,r=100005;
    //二分判定花费mid是否可行 
    while(l<r)
    {
        long long mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    if(l==100005)cout<<-1;
    else cout<<l;
    return 0;
}

 

如何优化？

 

继续思考，很容易发现，当阶段 i 增大时，候选集合在整体的向右移。因此，此题实际上是一个移动区间求最值的问题，明显用单调队列来实现。

单调队列中的元素维护的值满足单调性，并且每个元素对应在原序列中的顺序必须单调递增。每一次区间的移动，队首就是最优解。

 

建立单调队列 q，执行以下步骤：

1. 对于每个阶段 i（此题中每个状态的转移直接对应一个阶段），将决策候选集合中的元素 j 从队尾插入单调队列。此题中是区间最大值，所以队首应为未过时的所有决策中最大值。内部决策单调递减；

2. 检查队首，排除过时决策；

3. 直接取队首作为当前状态的最优决策，实行转移；

4. 转移过后，判断分数是否已经大于 k，如果是，返回判定成功。

所有 j 的取值最多进队和出队一次，因此单次判定在线性复杂度实现。

 

时间复杂度降为 O(n*log(n))。

//38 lines of AC_code
long long n,d,k,f[500005],a[500005][2],q[500005],l=0,r=100005;
bool check(int g){
    memset(f,-,sizeof(f));
    memset(q,0,sizeof(q));
    long long x=max(d-g,(long long)1),s=d+g;
    long long head=1,tail=0,j=0;
    f[0]=0;
    //依次转移每个i 
    for(long long i=1;i<=n;i++){  
        //决策候选集合  
        while(a[i][0]-a[j][0]>=x&&j<i){
            if(f[j]>-99999999){
                //检查队尾单调性 
                while(f[q[tail]]<=f[j]&&head<=tail)tail--;
                q[++tail]=j;//符合单调性后，插入决策j
            }
            j++;
        }
        //检查队头是否过时 
        while(a[i][0]-a[q[head]][0]>s&&head<=tail)head++;
        if(head<=tail)f[i]=f[q[head]]+a[i][1];//实行决策 
        if(f[i]>=k)return true;
    }
    return false;
}
int main(){
    cin>>n>>d>>k;
    for(long long i=1;i<=n;i++)cin>>a[i][0]>>a[i][1]; 
    //二分判定花费mid个金币是否可行 
    while(l<r){
        long long mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    if(l==100005)cout<<-1;
    else cout<<l;
    return 0;
}

 

 

斜率优化

 

因为我懒，所以不简述题意了。

 

稍加思考就能够写出转移方程。我们对于每一个 i，都枚举所有的 j，看看能否转移即可。

 

结合前缀和、贪心和斜率单调性，此题可以延伸出三个重要优化。

 

前缀和优化

 

for(long long i=1;i<=n;i++){
    t_=read();t=max(t,t_);
    cnt[t_]++,sum[t_]+=t_;
}
for(long long i=1;i<t+m;i++)cnt[i]+=cnt[i-1],sum[i]+=sum[i-1];
//枚举状态，每个状态直接构成一个阶段
for(long long i=0;i<t+m;i++){
    f[i]=cnt[i]*i-sum[i];//边界
    //枚举决策
    for(long long j=0;j<=i-m;j++)
        //对决策进行状态转移
        f[i]=min(f[i],f[j]+(cnt[i]-cnt[j])*i-(sum[i]-sum[j]));
}
for(long long i=t;i<t+m;i++)ans=min(ans,f[i]);
printf("%lld",ans);

 

排除无用决策

 

根据贪心原理，发现如果状态 i 和决策 j 之间的间距超过 2m，则在它们中间足以插入一趟运输，并且显然不劣于 j 作为决策进行转移。

因此，内层循环枚举决策点 j 的时候，无需从头开始，只需从 2m-1 开始。

long long n,m,t,t_,cnt[4000005],sum[4000005],ans=999999999999999,f[100005];
int main(){
    cin>>n>>m;
    for(long long i=1;i<=n;i++){
        t_=read();t=max(t,t_);
        cnt[t_]++,sum[t_]+=t_;
    }
    for(long long i=1;i<t+m;i++)cnt[i]+=cnt[i-1],sum[i]+=sum[i-1];
    for(long long i=0;i<t+m;i++){
        f[i]=cnt[i]*i-sum[i];
        for(long long j=max(i-m-m-1,(long long)(0));j<=i-m;j++)
            f[i]=min(f[i],f[j]+(cnt[i]-cnt[j])*i-(sum[i]-sum[j]));
    }
    for(long long i=t;i<t+m;i++)ans=min(ans,f[i]);
    printf("%lld",ans);
    return 0;
}

 

斜率优化

在这里LaTeX实在是没法打，所以抱歉从我的博客上截图了。

 

 

当然这只是dp优化的入门。我团队将会接着讲解dp优化。