主要内容
形如这样 的 \(\operatorname{DP}\) 转移方程：
\[dp[i]=\max_{L_i\le j\le R_i}{\{dp[i]+val(i,j)\}} \]满足：
-
\(\{L_i\}\) , \(\{R_i\}\) 递增（ 前提条件 ）。
-
\(R_i \le i\) （ 转移条件 ）。
-
\(val(i,j)\) 值只与 \(j\) 相关 （ 根本优化转移前提 ） 。
维护一个滑动窗口，每次求窗口中的最大值。对于两个点 \(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[i][j]=\max_{k=0}^{k\le k[i]}{\{dp[i-1][j-k\times c[i]]+k\times w[i]\}} \]考虑 \(dp\) 的转移 。
\[0\le p < c[i],0\le j \le \left\lfloor \dfrac{V-p}{c[i]}\right\rfloor,0\le k \le k[i] \] \[dp[i][p+j\times c]=\max{\{dp[i-1][p+(j-k)\times c]+k\times w\}} \] \[dp[i][p+j\times c]=\max{\{dp[i-1][p+(j-k)\times c]-(j-k)\times w+j\times w\}} \] \[dp[i][p+j\times c]=\max{\{dp[i-1][p+(j-k)\times c]-(j-k)\times w\}}+j\times w \]这样就可以进行单调队列优化了 。
时间复杂度：\(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})\) ，见背包问题 。
注意：
用结构体存储单调队列，防止反复修改 \(dp\) 值。
并注意 \(j=0\) 时的情况，及时更新。
例题
P1725 琪露诺
状态：设 \(dp[i]\) 表示走到 \(i\) 的最大收益。
\(L\) 与 \(R\) 都是上文中的转移范围。
核心代码：
n=rd(),tmpl=rd(),tmpr=rd();
for(int i=0;i<=n;i++) a[i]=rd();
for(int i=1;i<=n;i++) L[i]=i-tmpr,R[i]=i-tmpl;
memset(dp,-inf,sizeof(dp));
dp[0]=a[0];
for(int i=1;i<=n;i++) // 必须从 l 开始
{
if(R[i]<0) continue;
while(l<=r && q[l]<L[i]) l++;
while(l<=r && dp[q[r]]<=dp[R[i]]) r--;
q[++r]=R[i]; // 因为 i-L 小于 i ，所以应该确保最有决策再进行转移
dp[i]=dp[q[l]]+a[i];
}
int ans=-inf;
for(int i=L[n]+1;i<=n;i++) ans=max(ans,dp[i]);
printf("%d\n",ans);
P3572 [POI2014]PTA-Little Bird
状态：\(dp[i]\) 表示到 \(i\) 为止的最小代价。
核心代码：
bool Better(int x,int y)
{
if((dp[x]<dp[y]) || (dp[x]==dp[y] && h[x]>=h[y])) return true;
return false;
}
for(int i=1;i<=n;i++) L[i]=i-k,R[i]=i-1;
q[1]=l=r=1;
for(int i=2;i<=n;i++)
{
if(R[i]<0) continue;
while(l<=r && q[l]<L[i]) l++;
while(l<=r && Better(R[i],q[r])) r--;
q[++r]=R[i];
dp[i]=dp[q[l]]+(h[q[l]]<=h[i]);
}
printf("%d\n",dp[n]);
P3957 跳房子
\(\rightarrow\) P3957 solution
P1099 树网的核 \(\&\) P2491 [SDOI2011]消防（加强版 树网的核）
（多倍经验）
\(\rightarrow\) P1099 solution
CF372C Watching Fireworks is Fun
\(\rightarrow\) CF372C solution
烧桥计划
\(\rightarrow\) 烧桥计划 solution
P2254 [NOI2005]瑰丽华尔兹
\(\rightarrow\) P2254 solution
P2569 [SCOI2010]股票交易
\(\rightarrow\) P2569 solution