我仅一届平凡人对于某些dp的状态转移方程，我们可以写成一种形式：F[i]=minl(i)≤j≤r(i){F[j]+val(i,j)}F[i]=\min_{l(i)\leqj\leqr(i)}\{F[j]+val(i,j)\}F[i]=minl(i)≤j≤r(i){F[j]+val(i,j)}在这种模型中，j取值的范围都是关于i的一次单调函数val(i,j)val(i,j)val(i,j)是关于i，j的多项式函数。我们将其称为1D/1D的动态规划。在上述模型中，如果多项式val(x,y)val(x,y)val(x,y)的每一项仅与i或j中的一项有关，我们可以使用单调队列进行优化。李煜东蓝皮书上，给出三个例子。例1：
给定一个N长度的序列（有负数），选择一个长度不超过M的子段，使子段的所有数的和最大。
我处理出前缀和S[i]S[i]S[i]答案可以表述成：ans=max1≤i≤N{S[i]−mini−M≤j≤i−1{S[j]}}ans=\max_{1\lei\leN}\{S[i]-\min_{i-M\lej\lei-1}\{S[j]\}\}ans=max1≤i≤N{S[i]−mini−M≤j≤i−1{S[j]}}此时我们发现它符合上述模型。那么，我们是怎么通过单调队列进行优化的呢？我们不妨设两个位置j，k并满足：k<j<i。并且S[k]≥S[j]S[k]\geS[j]S[k]≥S[j]这时，我们可以知道：k绝对不可能是最优解。这不仅取决于j的前缀和比k小而j更优。还因为j的位置比k靠前（长度更短），我们在后期有更多的空间选择。此时我们将所有决策按照遍历顺序，维护成一个单调递增的队列。可以知道：最优子结构由且仅由队列中的决策产生。蓝皮书给出的代码：
intl=1,r=1;q[i]=0;for(inti=1;i<=n;i++){while(l<=r&&q[l]<i-m)l++;//弹出过时决策ans=max(ans,sum[i]-sum[q[l]]);//当前最优决策即位队头的值while(l<=r&&sum[q[r]]>=sum[i])r—-;//删除队尾决策保证单调性q[r++]=i;}
这个例子其实仅是一个单调队列的题目，不怎么涉及dp。例2：POJ1821Fence我们设F[i,j]F[i,j]F[i,j]为考虑前i个工匠，刷前j个木板，能获得的最大报酬。我们可以写成转移方程：F[i,j]=maxj−Li≤k≤Si−1{F[i−1,k],Pi∗(j−k)}F[i,j]=\max_{j-L_i\lek\leS_i-1}\{F[i-1,k],P_i*(j-k)\}F[i,j]=maxj−Li≤k≤Si−1{F[i−1,k],Pi∗(j−k)}这里注意摒弃i的干扰，这里的i只是表示阶段，不参与当前阶段的决策。这里的k是模型中的j，这里的j是模型中的i。对与每一个阶段，我们发现，随着j的递增，j−Lij-L_ij−Li线性递增，且val函数符合模型中的定义，可以使用单调队列优化！这时，我们随意找出两个位置k1,k2(k1<k2<Si−1)k_1,k_2(k_1<k_2<S_i-1)k1,k2(k1<k2<Si−1)且k2k_2k2的决策优于k1k_1k1此时k1k_1k1为完全无用的决策。所以我们依靠转移方程维护一个递减的单调队列。在这个题中，我们可以看到，首先对于每一个i阶段，我们初始化单调队列：
intl=1,r=0;for(intk=max(0,a[i].s-a[i].l);k<=a[i].s-1;k++){while(l<=r&&calc(i,q[r])<=calc(i,k))r--;q[++r]=k;}
我们在j−Li≤k≤Si−1j-L_i\lek\leS_i-1j−Li≤k≤Si−1的范围内初始化单调队列。因为右端点是不变的。我们只有缩左端点就行了。
for(intj=1;j<=n;j++){f[i][j]=max(f[i-1][j],f[i][j-1]);if(j>=a[i].s){while(l<=r&&q[l]<j-a[i].l)l++;if(l<=r)f[i][j]=max(f[i][j],calc(i,q[l])+a[i].p*j);}}
下面是完整ac代码：
#include<iostream>#include<cstring>#include<string>#include<queue>#include<vector>#include<algorithm>#include<cmath>#include<cstdio>usingnamespacestd;structNode{intl,p,s;}a[110];intf[110][16005],q[16005];boolcmp(Nodea,Nodeb){returna.s<b.s;}intcalc(inti,intk){returnf[i-1][k]-a[i].p*k;}intmain(){intn,m;cin>>n>>m;for(inti=1;i<=m;i++)scanf("%d%d%d",&a[i].l,&a[i].p,&a[i].s);sort(a+1,a+m+1,cmp);for(inti=1;i<=m;i++){intl=1,r=0;for(intk=max(0,a[i].s-a[i].l);k<=a[i].s-1;k++){while(l<=r&&calc(i,q[r])<=calc(i,k))r--;q[++r]=k;}for(intj=1;j<=n;j++){f[i][j]=max(f[i-1][j],f[i][j-1]);if(j>=a[i].s){while(l<=r&&q[l]<j-a[i].l)l++;if(l<=r)f[i][j]=max(f[i][j],calc(i,q[l])+a[i].p*j);}}}printf("%d\n",f[m][n]);return0;}
例3：O（nm）解多重背包。对于多重背包，我们处理朴素的计数，还可以通过二进制压缩进行优化，但是使用单调队列优化，我们可以讲复杂度衰减为O（nm）。我们通过模拟朴素多重背包发现：在每个阶段，每次状态的转移的位置都是成倍的。例如。对于ppp点，他只能转移到p+Vi,p+2∗Vi,p+3∗Vip+V_i,p+2*V_i,p+3*V_ip+Vi,p+2∗Vi,p+3∗Vi等，所以我们所有状态，按照%ViV_iVi的余数分为等价类。对于每一个余数uuu有状态转移方程：F[u+p∗Vi]=maxp−Ci≤k≤p−1{F[u+k∗Vi]+(p−k)∗Wi}F[u+p*V_i]=\max_{p-C_i\lek\lep-1}\{F[u+k*V_i]+(p-k)*W_i\}F[u+p∗Vi]=maxp−Ci≤k≤p−1{F[u+k∗Vi]+(p−k)∗Wi}同理符合上述模型。代码不想打了。。。直接看书吧。回头学一波斜率优化就ok了。。。。。。。
