单调队列优化DP

EricQian · 2020-08-20 15:57:38 · 个人记录

主要内容

形如这样 的 \operatorname{DP} 转移方程：

满足：

维护一个滑动窗口，每次求窗口中的最大值。对于两个点 x ，y ，如果 x < y 且 f(x) < f(y) ，那么 y 进入窗口后，决策点一定不会是 x 。

用一个单调队列维护窗口里所有可能用到的决策点。

窗口右端点向右滑动时，把一个新的点插入队尾。队尾点为 q[r] ，新点为 x ，如果 f(q[r]) \le f(x) ，那么 q[r] 没用，把 q[r] 弹掉。重复过程直到队尾点可能有用，即 f(q[r]) > f(x) ，把 x 入队。

队列中的 f(i) 从队首到队尾递减。决策时，首先弹掉队首超过范围的点。这时队首点就是决策点。f(i) = \max {\{f(j) + w_i\}} [i-R_i \le j \le i-L_i]

单调队列优化 也称为 滑动窗口 。

变式 - 单调队列优化多重背包

设 dp[i][j] 表示前 i 个物品放入容量为 j 的背包的最大收益 。

考虑 dp 的转移 。

这样就可以进行单调队列优化了 。

时间复杂度：O(nV) 。

核心代码：（ P1776 宝物筛选 ） 代码中的 pos 就是上面的 j-k 。

struct Data{ int pos,val; }q[Maxv];

n=rd(),V=rd();
for(int i=1;i<=n;i++)
{
     w=rd(),c=rd(),sum=rd();
     if(!c) { ans+=w*sum; continue; }
     sum=min(V/c,sum);
     for(int p=0;p<c;p++)
     {
         s=(V-p)/c,l=1,r=0;
         for(int j=0;j<=s;j++)
         {
             while(l<=r && q[r].val<=dp[p+j*c]-j*w) r--;
             q[++r]=(Data){j,dp[p+j*c]-j*w};
             while(l<=r && j-q[l].pos>sum) l++; // k>sum 时不合法 
             dp[p+j*c]=max(dp[p+j*c],q[l].val+j*w);
         }
     }
}
printf("%d\n",ans+dp[V]);

多重背包的其他解法：二进制分组优化 ，时间复杂度： O(V\sum_{i=1}^{n}\log_2{k_i}) ，见背包问题 。

例题

• P1725 琪露诺

状态：设 dp[i] 表示走到 i 的最大收益。