这段时间在重温DP，发现DP中有很大很重要的一块区域是关于DP优化的，于是来和大家分享一下各种DP优化方法，下面讲一下单调队列优化DP
- 单调队列
首先来重温下什么是单调队列，在单调队列中，每个元素的决策时间单调增而它的决策单调更劣，这就显然可以明白，最优决策永远在队首。
如果对上面基础单调队列不了解，可以先做【POJ2823】Sliding Window 这道题目体会一下再回来看后面的重点，这里就不再赘述了。
- 单调队列优化DP
在单调队列中，当区间移动时，在队头不停删除不在区间内的决策，而在队尾加入决策，在队尾加入决策前要判断是否满足单调性，否则先删除队尾决策直到加入决策后能满足单调性再加入。
下面来一道例题【POJ1821】
题意：有K个工人，和长为N的篱笆，现在要给篱笆上色。每个工人坐在Si上，他能刷的最大范围是Li，且必须是一个连续子区间，而且必须过Si，他刷完后能获得Pi钱，求总报酬最大值
思路：先设出方程，设 dp[i][j] 表示前i个工人，前 j 个篱笆的最大获利
那么dp[i][j]=dp[i-1][j]（第i个人不刷）或dp[i][j]=dp[i][j-1] （第i个人不刷第j 块）
状态转移方程是 dp[i][j] = max( dp[i][j] ，dp[i-1][k] + (j-k)*P[i] ) j>=S[i]，k<S[i] 且k>=j - L[i]
把加粗的那一段展开得到dp[i-1][k] - k*P[i] + j*P[i] 那么这样，前半部分只与决策k有关（除状态i），这样的话随j的增大，k取值范围下界在增大，上届不变，所以k越大时存活时间越长，而这时如果还满足前面加粗式的单增，则不难想到，可以用单调队列优化，优化后时间复杂度为O(NM)
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define N 120
#define M 17000
using namespace std;
struct AC
{
int l,p,s;
}re[N];
int q[M],l[N],r[N],dp[N][17000],n,k;
inline bool cmp(const AC &a,constAC &b)
{
return a.s<b.s;
}
void solve()
{
for(int i=0;i<=n;i++) dp[0][i]=0;
for(int i=1;i<=k;i++)
{
for(int j=0;j<re[i].s;j++) dp[i][j]=dp[i-1][j]; //第i个粉刷匠不刷任何墙
int h=0,t=0;
for(int j=l[i],tmp;j<re[i].s;j++) //将dp[i-1]层的最优状态存入单调队列
{
tmp=dp[i-1][j]-j*re[i].p;
while(t>h&&dp[i-1][q[t-1]]-q[t-1]*re[i].p<=tmp) t--;
q[t++]=j;
}
for(int j=re[i].s,tmp;j<=r[i];j++)
{
while(t>h&&j-q[h]>re[i].l) h++; //弹出不在范围中的元素
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
dp[i][j]=max(dp[i][j],dp[i-1][q[h]]+(j-q[h])*re[i].p);
}
for(int j=r[i]+1;j<=n;j++) dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,dp[k][i]);
printf("%d
",ans);
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
for(int i=1;i<=k;i++)
scanf("%d%d%d",&re[i].l,&re[i].p,&re[i].s);
sort(re+1,re+1+k,cmp);
for(int i=1;i<=k;i++)
{
l[i]=max(0,re[i].s-re[i].l);
r[i]=min(n,re[i].s+re[i].l-1);
}
solve();
}
return 0;
}