单调队列优化dp
对于一些比较简单的题目，我们可以直接凭借经验进行优化。
但是对于类似\(max(f[j-kw]+kv)\)(多重背包)我们就很难凭借经验找到优化方式了
这个时候，我们就可以尝试一下下面的方法：
我们观察一些简单的，可以单调队列优化的方程，他们都有这样的形式：
\(max/min(g[i-k])(L\leq k \leq R)\),这个时候我们就可以考虑对g数组单调队列
也就是我们要构造出这个g数组
使用待定系数法，我们可以将g数组写成\(g[B][x]=f[Ax+B]+Cx+D\)
至于B的大小，如果存在\(B_n=A\)的话，\(B=0,x=1\)和\(B=B_n=A,x=0\)对应的是同一个f数组，就会有一些\(f[Ax+b]\)重复入队出队，而一般而言我们只能进一次出一次，否则会导致复杂度的出错
因此我们有\(0\leq B < A\),且对于一个j,有且仅有一个x与之对应
我们要把\(f[j-kw]+kv\)与\(g[B][x]\)一一对应，计算时，对于不同的k，我们就取\(j-kw\)对应的x
也就是要把\(f[j-kw]+kv\)与\(f[Ax+B]+Cx+D\)一一对应
对于\(f[j]\)来说，我们迟早会有一个\(x_{now}\)，使得\(f[j]=g[x_{now}]\)
因此我们取k=0或1(虽然不一定在单调队列的符合的范围)
所以我们就有
\[\left\{ \begin{aligned} &j-0*w=Ax_{now}+B\\ &j-1*w=A(x_{now}-1)+B\\ &0*v=Cx_{now}+D\\ &1*v=C(x_{now}-1)+D\\ \end{aligned} \right.\\ \]算出
\[\left\{ \begin{aligned} &A=w\\ &B=j-0*w-Ax_{now}=j-wx_{now}=j\%w\\ &C=-v\\ &D=0*v-Cx_{now}=vx_{now} \end{aligned} \right.\\ \]最终我们就将\(max(f[j-kw]+kv)\)转化成了\(max(g[B][x])\),就是\(max(f[w*x+j\%w]+(-v)*x+vx_{now})\)
这里我们要注意一下\(x\)和\(x_{now}\)的区别，计算同一条式子时，\(x\)是会变的，但是\(x_{now}\)是不会变的
最后就是取值范围的问题，一开始我们有\(L\leq k \leq R\),
\(k=0\)时，\(f[j-kw]=f[j-0*w]=f[j]\)对应\(g[B][x_{now}]\)
\(k=1\)时，\(f[j-kw]=f[j-1*w]=f[j-w]\)对应\(g[B][x_{now}-1]\)
...
\(k=L\)时，\(f[j-kw]=f[j-L*w]\)对应\(g[B][x_{now}-L]\)
\(k=R\)时，\(f[j-kw]=f[j-R*w]\)对应\(g[B][x_{now}-R]\)
所以x的取值范围是\(x_{now}-R\leq x \leq x_{now}-L\)
最终，对于单调队列，为了避免初始化的问题，
我们可以先添上新的符合条件的数\((x_{now}-L)\),更新优先队列
注意我们要判断一下\((x_{now}-L)\)有没有意义
然后退出不符合条件的数，这样即使新增加的数不符合条件（如距离）也会被弹出去
之后才计算答案
对于一些复杂的单调队列，最好先写朴素dp，再进行优化
例题
放假
经过几个月辛勤的工作，FJ决定让奶牛放假。
假期可以在1…N天内任意选择一段（需要连续），每一天都有一个享受指数W。
但是奶牛的要求非常苛刻，假期不能短于P天，否则奶牛不能得到足够的休息；
假期也不能超过Q天，否则奶牛会玩的腻烦。
FJ想知道奶牛们能获得的最大享受指数。
输入格式
第一行：N,P,Q.
第二行：N个数字，中间用一个空格隔开。
数据范围：
50% 1≤N≤10000
100% 1≤N≤100000
１ <= p <= q <= n
输出格式
一个整数，奶牛们能获得的最大享受指数
分析
朴素dp方程：\(f[i]=s[i]-min(s[k])(i-q\leq k\leq i-p)或f[i]=s[i]-min(s[i-k])(p\leq k\leq q)\)
一般来说，对于第一个方程，我们已经可以直接优化了
但是尝试一下新的做法
我们解得\(A=1,B=0,C=0,D=0\)
我们还知道\(x_{now}=i，L=p,R=q\)
\(x_{add}=x_{now}-L\)
然后就差不多做完了
代码
方法一：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
int maxx=-(1e9+9),n,P,Q,a[maxn],s[maxn],f[maxn],q[maxn],st=1,en=0;
signed main(){
scanf("%lld%lld%lld",&n,&P,&Q);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;i++){
int now=i-P;
if(now<0)continue;
while(st<=en&&s[q[en]]>=s[now])en--;
while(st<=en&&q[st]<i-Q)st++;
en++,q[en]=now;
f[i]=s[i]-s[q[st]];
maxx=max(maxx,f[i]);
}
cout<<maxx;
return 0;
}
方法二：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
int a[maxn],s[maxn],n,P,Q,q[maxn],maxx=-1e9-9;
int calc(int A,int B,int C,int D,int x){
return s[A*x+B]+C*x+D;
}
signed main(){
cin>>n>>P>>Q;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
int st=1,en=0;
for(int i=1;i<=n;i++){
int A=1,B=0,C=0,D=0;
int X=i,L=P,R=Q;
int add_X=X-L;
if(add_X<0)continue;
while(st<=en&&calc(A,B,C,D,q[en])>=calc(A,B,C,D,add_X))en--;
q[++en]=add_X;
while(st<=en&&q[st]<X-R)st++;
maxx=max(maxx,s[i]-calc(A,B,C,D,q[st]));
}
cout<<maxx<<endl;
return 0;
}
实际上B,C,D现在没用，所以可以优化一下
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
int a[maxn],s[maxn],n,P,Q,q[maxn],maxx=-1e9-9;
int calc(int x){
return s[x];
}
signed main(){
cin>>n>>P>>Q;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
int st=1,en=0;
for(int i=1;i<=n;i++){
int X=i,L=P,R=Q;
int add_X=X-L;
if(add_X<0)continue;
while(st<=en&&calc(q[en])>=calc(add_X))en--;
q[++en]=add_X;
while(st<=en&&q[st]<X-R)st++;
maxx=max(maxx,s[i]-calc(q[st]));
}
cout<<maxx<<endl;
return 0;
}
松果
有N棵松果树从左往右排一行，桃桃是一只松鼠，它现在在第一棵松果树上。
它想吃尽量多的松果，但它不想在地上走，而只想从一棵树跳到另一棵树上。
松鼠的体力有个上限，每次不能跳的太远，也不能跳太多次。
每当它跳到一棵树上，就会把那棵树上的松果全部都吃了。
它最多能吃到多少个松果？
输入格式
第一行，三个整数：N、D、M。N表示松果树的数量，
D表示松鼠每次跳跃的最大距离，M表示松鼠最多能跳跃M次。
接下来有N行，每行两个整数：Ai和Bi。
其中Ai表示第i棵树上的松果的数量，Bi表示第i棵树与第1棵树的距离，其中B1保证是0。
数据保证这N棵树从左往右的次序给出，即Bi是递增的，不存在多棵树在同一地点。输出格式
一个整数。
【数据范围】
Ai <= 10000, D <= 10000
对于40%的数据，M<N<= 100, Bi <= 10000
对于100%的数据，M < N <= 2000, Bi <= 10000
分析
这题和上一题很类似，A=1,B=0,C=0,D=0
新增加的数为\(x_{add}=j-1\)
至于距离，我们要判断的是\(A*q[st]+B\)到\(A*x_{now}+B\)的距离，就不要用朴素方程的来判断了
代码
方法一：
#include<bits/stdc++.h>
using namespace std;
const int maxn=2*1e3+5;
int n,d,m,a[maxn],b[maxn],f[maxn][maxn];
int q[maxn],st,en,maxx=0;
int main(){
scanf("%d%d%d",&n,&d,&m);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
memset(f,-0x3f,sizeof f);
f[0][1]=a[1];
for(int i=1;i<=m;i++){
st=1,en=0;
for(int j=1;j<=n;j++){
int k=j-1;
if(k<1)continue;
while(st<=en&&b[j]-b[q[st]]+1>d)st++;
while(st<=en&&f[i-1][q[en]]<f[i-1][k])en--;
en++,q[en]=k;
f[i][j]=f[i-1][q[st]]+a[j];
maxx=max(maxx,f[i][j]);
}
}
cout<<maxx;
return 0;
}
方法二：
#include<bits/stdc++.h>
using namespace std;
const int maxn=2*1e3+5;
int n,d,m,a[maxn],b[maxn],f[maxn][maxn];
int q[maxn],st,en,maxx=0;
int calc(int A,int B,int C,int D,int x,int whi){
return f[whi][A*x+B]+C*x+D;
}
int main(){
scanf("%d%d%d",&n,&d,&m);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
memset(f,-0x3f,sizeof f);
f[0][1]=a[1];
for(int i=1;i<=m;i++){
st=1,en=0;
for(int j=1;j<=n;j++){
int A=1,B=0,C=0,D=0;
int X=j;
int add_X=j-1;
if(add_X<=0)continue;
while(st<=en&&calc(A,B,C,D,q[en],i-1)<=calc(A,B,C,D,add_X,i-1))en--;
q[++en]=add_X;
while(st<=en&&b[A*q[st]+B]<b[A*X+B]-d)st++;
f[i][j]=a[j]+calc(A,B,C,D,q[st],i-1);
maxx=max(maxx,f[i][j]);
}
}
cout<<maxx;
return 0;
}
P2254 [NOI2005] 瑰丽华尔兹
分析
难度不大，主要是简化代码
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=205;
int n,m,X,Y,K,f[maxn][maxn][maxn],x,y,op,maxx=0,qx[maxn],qy[maxn],qz[maxn];
int dirx[]={0,-1,1,0,0};
int diry[]={0,0,0,-1,1};
bool mp[maxn][maxn];
char c[205];
bool check(int x,int y){
return 1<=x&&x<=n&&1<=y&&y<=m;
}
void work(int x,int y,int whi,int len,int pos){
int st=1,en=0;
for(int i=1;check(x,y);i++,x+=dirx[whi],y+=diry[whi]){
if(!mp[x][y]){st=1,en=0;continue;}
while(st<=en&&f[pos-1][qx[en]][qy[en]]+i-qz[en]<=f[pos-1][x][y])en--;
while(st<=en&&abs(x-qx[st])+abs(y-qy[st])>len)st++;
en++,qx[en]=x,qy[en]=y,qz[en]=i;
f[pos][x][y]=f[pos-1][qx[st]][qy[st]]+i-qz[st];
}
}
int main(){
scanf("%d%d%d%d%d",&n,&m,&X,&Y,&K);
memset(mp,true,sizeof mp);
for(int i=1;i<=n;i++){
scanf("%s",c);
for(int j=1;j<=m;j++){
if(c[j-1]=='x')mp[i][j]=false;
}
}
memset(f,-0x3f,sizeof f);
f[0][X][Y]=0;
for(int whi=1;whi<=K;whi++){
scanf("%d%d%d",&x,&y,&op);
y=y-x+1;
if(op==1)for(int i=1;i<=m;i++)work(n,i,op,y,whi);
if(op==2)for(int i=1;i<=m;i++)work(1,i,op,y,whi);
if(op==3)for(int i=1;i<=n;i++)work(i,m,op,y,whi);
if(op==4)for(int i=1;i<=n;i++)work(i,1,op,y,whi);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
maxx=max(maxx,f[K][i][j]);
cout<<maxx<<endl;
return 0;
}
P1776 宝物筛选
分析
多重背包，绝大部分分析就在最开头
实际上，B的意义就是，你要开B+1条单调队列
在打代码的时候，我们会发现我们无法同时开下多个单调队列
因此我们考虑一条一条队列处理，其他的就不难了
由于是单调队列优化，我们不可以逆着过来做，而我们先计算出的答案又会影响后面的答案
因此我们用滚动数组避免这个问题
顺便也把二进制拆分的代码贴上去（思想就是一个数拆成一位一位的二进制，最后剩下的再额外算）
代码
二进制优化
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=4*1e4+5;
int maxx=0,f[maxn],n,W,v,w,m;
void solve(int v,int w){
for(int i=W;i>=w;i--)f[i]=max(f[i-w]+v,f[i]),maxx=max(maxx,f[i]);
}
signed main(){
scanf("%lld%lld",&n,&W);
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld",&v,&w,&m);
int M=1;
while(M<=m){
solve(v*M,w*M);
m-=M;
M*=2;
}
if(m!=0)
solve(v*m,w*m);
}
cout<<maxx;
return 0;
}
单调队列优化
#include<bits/stdc++.h>
using namespace std;
const int maxn=4*1e4+5;
int dp[2][maxn],n,W,v,w,m,st,en,q[maxn],maxx=0,whi;
inline int calc(int A,int B,int C,int D,int whi,int x){
return dp[whi][A*x+B]+C*x+D;
}
int main(){
memset(dp,-0x3f,sizeof dp);
dp[1][0]=0;whi=1;
cin>>n>>W;
for(int i=1;i<=n;i++){
cin>>v>>w>>m;
whi=!whi;
for(int j=0;j<w;j++){
st=1,en=0;
for(int k=j;k<=W;k+=w){
int X=k/w;
int L=0,R=m,A=w,B=j,C=-v,D=(L+X)*v;
int add_X=X-L;
while(st<=en&&calc(A,B,C,D,!whi,q[en])<=calc(A,B,C,D,!whi,add_X))en--;
q[++en]=add_X;
while(st<=en&&q[st]<X-R)st++;
int used_X=q[st];
dp[whi][A*X+B]=max(dp[!whi][A*X+B],calc(A,B,C,D,!whi,used_X));
maxx=max(maxx,dp[whi][A*X+B]);
}
}
}
cout<<maxx;
return 0;
}
P1070 [NOIP2009 普及组] 道路游戏
分析
一样是先写出朴素dp，优化时我们要注意：
我们增加数的时候，转移方程是依附于之前的（包括现在的）时间节点的数组f的最终的答案
因此我们要先计算出最终答案再增加数
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
int n,m,p,a[maxn][maxn],f[maxn],pay[maxn],s[maxn][maxn],st[maxn],en[maxn],q1[maxn][maxn],q2[maxn][maxn];
int change(int x){
x=(x%n+n)%n;
return x;
}
int main(){
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[j][i]);
if(i==n)a[j][0]=a[j][i];
}
}
for(int i=0;i<n;i++)scanf("%d",&pay[i]);
for(int i=1;i<=m;i++){
for(int j=0;j<n;j++){
s[i][j]=s[i-1][change(j-1)]+a[i][j];
}
}
for(int i=0;i<n;i++)st[i]=1,en[i]=0;
memset(f,-0x3f,sizeof f);
f[0]=0;
for(int T=0;T<=m;T++){
for(int i=0;i<n;i++){
int whi=((i-T)%n+n)%n;
while(st[whi]<=en[whi]&&q2[whi][st[whi]]+p<T)st[whi]++;
if(st[whi]<=en[whi])f[T]=max(f[T],q1[whi][st[whi]]+s[T][i]);
}
for(int i=0;i<n;i++){
int whi=((i-T)%n+n)%n;
while(st[whi]<=en[whi]&&q1[whi][en[whi]]<=f[T]-s[T][i]-pay[i])en[whi]--;
en[whi]++,q1[whi][en[whi]]=f[T]-s[T][i]-pay[i],q2[whi][en[whi]]=T;
}
}
cout<<f[m];
return 0;
}
P3957 [NOIP2017 普及组] 跳房子
分析
对于这一题，我们还是采用两种方法，不过对于第二种方法，我们要额外记录一个last入队
其他差不多
代码
方法一：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5*1e5+5;
int n,d,k,a[maxn],b[maxn];
int q1[maxn],q2[maxn],st1,st2,en1,en2;
int f[maxn];
signed main(){
cin>>n>>d>>k;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
int l=-1,r=1e17;
while(l+1<r){
int mid=(l+r)/2;
int L=max(1ll,d-mid),R=d+mid;
st1=1,st2=1,en1=0,en2=1;
q2[st2]=0;
bool flag=false;
for(int i=1;i<=n;i++){
while(st2<=en2&&a[q2[st2]]+L<=a[i]){
while(st1<=en1&&f[q1[en1]]<=f[q2[st2]])en1--;
q1[++en1]=q2[st2++];
}
while(st1<=en1&&a[q1[st1]]+R<a[i])st1++;
if(st1<=en1){
f[i]=f[q1[st1]]+b[i];
if(f[i]>=k){
flag=true;
break;
}
q2[++en2]=i;
}
}
if(flag)r=mid;
else l=mid;
}
if(r==1e17)r=-1;
cout<<r<<endl;
return 0;
}
方法二：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5*1e5+5;
int n,d,k,a[maxn],b[maxn];
int q[maxn],st,en;
int f[maxn];
bool vis[maxn];
int calc(int A,int B,int C,int D,int x){
return f[A*x+B]+C*x+D;
}
signed main(){
cin>>n>>d>>k;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
int l=-1,r=1e17;
while(l+1<r){
int mid=(l+r)/2;
int L=max(1ll,d-mid),R=d+mid;
st=1,en=0;
bool flag=false;
int last=0;
for(int i=1;i<=n;i++){
f[i]=0;
vis[i]=false;
int A=1,B=0,C=0,D=0;
int X=i;
while(last<i&&a[last]<=a[X]-L){
int add_X=last;
if(!vis[add_X]){
last++;
continue;
}
while(st<=en&&calc(A,B,C,D,q[en])<=calc(A,B,C,D,add_X))en--;
q[++en]=add_X;
last++;
}
while(st<=en&&a[q[st]]<a[X]-R)st++;
if(st<=en)
f[A*X+B]=f[A*q[st]+B]+b[i],vis[A*X+B]=true;
if(f[A*X+B]>=k){
flag=true;
break;
}
}
if(flag)r=mid;
else l=mid;
}
if(r==1e17)r=-1;
cout<<r<<endl;
return 0;
}