动态规划的不同优化方式-1:单调队列
先来看一道例题：最大子序和
题目描述
有一个序列a[1],a[2],......,a[n],求其中长度<=m的最大连续子序列和.
朴素解法
子序列和
$$ a[i]+a[i+1]+…+a[j] $$
可以表示为前缀和之差
$$ s[j]-s[i-1] $$
其中，
$$
s[x] = \sum_{i=1} ^ x a[i]
$$
(规定s[0]=0)
对于每一个i，我们只需要求出满足
$$ 1<=i-j<=m $$
的最大的
$$ s[i]-s[j] $$
即s[i]减去最小的s[j]。
由于n太大，不可能暴力枚举所有符合条件的j。
优化
是否可以使用一个数据结构，支持如下几种操作：
- 插入一个数s[j]及其进入时间j(insert)
- 删去当前时间i-进入时间>m的数(remove)
- 求出剩余数中的最小值(select)
我们看一下每个数在什么情况下可能被select到
如果两个数a,b和它们的进入时间ta,tb(ta<tb)满足
$$ a>b $$
那么，由于a比b大且a比b被删去的还早，所以，只要有b，a就一定不会成为最优决策。
那么不如直接把a删除。
因此，我们可以用一个队列来维护（用数组q模拟队列，队列中保存数组下标，队头队尾分别为ql和qr）
队列中第i个和第j个(i<j)满足第i个的值和进入时间均比第j个要小
如何维护呢？
删除过时决策：从队头删除
while(ql<=qr&&i-q[ql]>m) ql++;
取出最小值：直接取队头
插入一个数i：从队尾插入（保证进入时间按升序排序），插入时维护一下队尾s单调性
while(ql<=qr&&s[q[qr]]>=s[i]) qr--;
这就是单调队列算法
代码实现：
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef long long ll;
int n,m,q[N],ql,qr;
ll s[N];
int main(){
cin>>n>>m;
for (int i=1;i<=n;i++) {
cin>>s[i];
s[i]+=s[i-1];
}
ll res=INT_MIN;
ql=qr=1;
q[1]=0;//初始决策
for (int i=1;i<=n;i++) {
while(ql<=qr&&i-q[ql]>m) ql++;
res=max(res,s[i]-s[q[ql]]);
while(ql<=qr&&s[q[qr]]>=s[i]) qr--;
qr++;
q[qr]=i;
}
cout<<res<<endl;
return 0;
}
再来看一道单调队列优化DP题：围栏
题目描述
有N块木板从左到右排成一行，有M个工匠对这些木板进行粉刷，每块木板至多被粉刷一次。第 i 个木匠要么不粉刷，要么粉刷包含木板S[i]的，长度不超过L[i]的连续的一段木板，每粉刷一块可以得到P[i]的报酬。
不同工匠的S[i]不同。
请问如何安排能使工匠们获得的总报酬最多。
普通DP解法
先把所有工匠按照S[i]排序。这样每位工匠的粉刷区间一定在上一位粉刷区间之后。
设F[i,j]表示前i个人刷前j块木板能得到的最多报酬。（可以有空着不刷的木板）
1.第i位木匠可以什么也不刷，F[i,j]=F[i-1,j]
2.第j块木板可以空着不刷，F[i,j]=F[i,j-1]
3.第i个人刷第k+1~j块木板。
$$ F[i,j] = \max_{j-L_i \leq S_i-1} (F[i-1,k]+P_i*(j-k)) $$
当j增大时，k的上限不变，而k的下界会变化。
将F[i,j]中所有和j有关与和k有关的项分离开来
$$ F[i,j] = P_i * j + \max_{j-L_i \leq k \leq S_i-1} (F[i-1,k]-P_i*k) $$
定义
$$ ch(i,k)=F[i-1][k]-P_i*k $$
我们可以使用单调队列：
1.j开始枚举之前，先把所有的k插入单调队列。
for(int k=max(0,s[i]-l[i]);k<=s[i]-1;k++){
while(l<=r&&ch(i,q[r])<=ch(i,k)) r--;
q[++r]=k;
}
2.每次删去过时决策
if(s[i]<=j){
while(l<=r&&j-q[l]>l[i]) l++;
if(l<=r) f[i][j]=max(f[i][j],ch(i,q[l])+p[i]*j);
}
代码实现（为了方便排序，把每一个工匠的所有属性封装进了结构体）：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct dd{int l,p,s;}a[105];
int n,m,f[105][16005],q[16005],res;
bool cmp(dd x,dd y){return x.s<y.s;}//比较函数：按s排序
int ch(int i,int k){return f[i-1][k]-a[i].p*k;}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>a[i].l>>a[i].p>>a[i].s;
sort(a+1,a+1+m,cmp);
for(int i=1;i<=m;i++){
int l=1,r=0;
for(int k=max(0,a[i].s-a[i].l);k<=a[i].s-1;k++){
while(l<=r&&ch(i,q[r])<=ch(i,k)) r--;
q[++r]=k;
}
for(int j=1;j<=n;j++){
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(a[i].s<=j){
while(l<=r&&j-q[l]>a[i].l) l++;
if(l<=r) f[i][j]=max(f[i][j],ch(i,q[l])+a[i].p*j);
}
}
}
for(int i=1;i<=n;i++) res=max(res,f[m][i]);//求max
cout<<res<<endl;
return 0;
}
练习题：
- 多重背包问题 III （较难，多思考，提示：要用到余数）
- 干草堆
- 股票交易
很赞啊