单调队列优化dp学习笔记

队列优化dp学习笔记"/>

单调队列优化dp学习笔记

这类问题一般是朴素的复杂度大的转移很好写。
然后转移类似rmq的问题。

需要注意的是：在新值与队头元素判断谁更优的时候，需要把两者放在一个参考系下进行比较。
就是 把旧值等效放在新值的位置上的值才是旧值的真实值。

cf372C
题意：给你m个烟花，每个烟花在t_i时刻在x位置被点燃，得到b_i+|a_i-x|的分，初始选择任意位置，每分钟移动一个单位。问最大得分是多少。
根据题目可以写出一个暴力的dp

for(int i=2;i<=m;i++){for(int j=1;j<=n;j++){int ti=t[i]-t[i-1];int l=max(1,j-ti*d);int r=min(n,j+ti*d);for(int pos=l;pos<=r;pos++){dp[i][j]=max(dp[i][j],dp[i-1][pos]+b[i]+abs(a[i]-j));}}
}

观察可以发现，后面一坨 d p [ i − 1 ] [ p o s ] + b [ i ] + a b s ( a [ i ] − j ) dp[i-1][pos]+b[i]+abs(a[i]-j) dp[i−1][pos]+b[i]+abs(a[i]−j)是可以单独计算的。。
那么就是要求出 l , r l,r l,r范围内的最大dp值即可。
搞个单调队列就行。
可以用滚动数组优化一下空间。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define wzh(x) cout<<#x<<' '<<x<<endl
int n,m,d;
LL dp[2][N];
pair<LL,int> q[N];
LL ans=-1e18;
struct uzi{int a,b,c;	
}p[N];
int main() {ios::sync_with_stdio(false);cin>>n>>m>>d;for(int i=1;i<=m;i++)cin>>p[i].a>>p[i].b>>p[i].c;for(int i=1;i<=n;i++){dp[0][i]=p[1].b-abs(p[1].a-i);}int st=1;for(int i=2;i<=m;i++){//从前后 [j-d,j+d]int l=1,r=0;for(int j=1;j<=n;j++){LL nd=p[i].b-abs(p[i].a-j) ;int dis=p[i].c-p[i-1].c;int _l=max(1ll,j-1ll*dis*d);int _r=min(1ll*n,j+1ll*dis*d);while(l<=r&&q[l].se<_l){l++;}for(int j=q[r].se+1;j<=_r;j++){while(l<=r&&q[r].fi<dp[st^1][j]){r--;}q[++r]={dp[st^1][j],j};}dp[st][j]=q[l].fi+nd;// 窗口//find mininum dp[i-1][x] where x in range of [l,r]}st^=1;}st^=1;for(int i=1;i<=n;i++){ans=max(ans,dp[st][i]);}cout<<ans<<'\n';return 0;
}

luogu2254

记录一下四个方向上第一次遇到障碍的位置。
然后分四个方向转移就行。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define wzh(x) cerr<<#x<<' '<<x<<endl
int dp[202][202][202];
pair<int,int>q[N];
int n,m,x,y,ka;
char a[202][202];
int s[N],t[N],d[N];
int sh[202][202],xa[202][202];
int zo[202][202],yo[202][202];
int main() {ios::sync_with_stdio(false);cin>>n>>m>>x>>y>>ka;for(int i=1;i<=n;i++){cin>>a[i]+1;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){zo[i][j]=zo[i][j-1];if(a[i][j]=='x')zo[i][j]=j;}yo[i][m+1]=m+1;for(int j=m;j>=1;j--){yo[i][j]=yo[i][j+1];if(a[i][j]=='x')yo[i][j]=j;}}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){sh[j][i]=sh[j-1][i];if(a[j][i]=='x')sh[j][i]=j;}xa[n+1][i]=n+1;for(int j=n;j>=1;j--){xa[j][i]=xa[j+1][i];if(a[j][i]=='x')xa[j][i]=j;}}memset(dp,-0x3f3f3f,sizeof dp);dp[0][x][y]=0;for(int i=1;i<=ka;i++){cin>>s[i]>>t[i]>>d[i];}for(int i=1;i<=ka;i++){if(d[i]==4){for(int j=1;j<=n;j++){int l=1,r=0;for(int k=1;k<=m;k++){if(a[j][k]=='x'){l=1,r=0;	}else{int _l=max(1,k-(t[i]-s[i]+1));//从 左边 转移过来的_l=max(_l,zo[j][k]+1);// 第一个 障碍物 右边 while(l<=r&&q[l].se<_l)l++;for(int _q=(l<=r?q[r].se+1:_l);_q<=k;_q++){while(l<=r&&q[r].fi+abs(_q-q[r].se)<dp[i-1][j][_q])r--;q[++r]={dp[i-1][j][_q],_q};}dp[i][j][k]=q[l].fi+abs(k-q[l].se);}}}  			}else if(d[i]==3){for(int j=1;j<=n;j++){int l=1,r=0;for(int k=m;k>=1;k--){if(a[j][k]=='x'){l=1,r=0;	}else{int _l=min(m,k+(t[i]-s[i]+1));_l=min(_l,yo[j][k]-1);while(l<=r&&q[l].se>_l)l++;for(int _q=(l<=r?q[r].se-1:_l);_q>=k;_q--){while(l<=r&&q[r].fi+abs(_q-q[r].se)<dp[i-1][j][_q])r--;q[++r]={dp[i-1][j][_q],_q};}dp[i][j][k]=q[l].fi+abs(k-q[l].se);if(i==4){//	cout<<"deb";//cout<<j<<' '<<k<<' '<<q[l].se<<' '<<dp[i][j][k]<<' '<<_l<<endl;}}}}  }else if(d[i]==2){for(int j=1;j<=m;j++){int l=1,r=0;for(int k=1;k<=n;k++){if(a[k][j]=='x'){l=1,r=0;}else{int _l=max(1,k-(t[i]-s[i]+1));_l=max(_l,sh[k][j]+1);while(l<=r&&q[l].se<_l)l++;for(int _q=(l<=r?q[r].se+1:_l);_q<=k;_q++){while(l<=r&&q[r].fi+abs(_q-q[r].se)<dp[i-1][_q][j])r--;q[++r]={dp[i-1][_q][j],_q};}dp[i][k][j]=q[l].fi+abs(k-q[l].se);}}}}else{for(int j=1;j<=m;j++){int l=1,r=0;for(int k=n;k>=1;k--){if(a[k][j]=='x'){l=1,r=0;}else{int _l=min(n,k+(t[i]-s[i]+1));_l=min(_l,xa[k][j]-1);while(l<=r&&q[l].se>_l)l++;for(int _q=(l<=r?q[r].se-1:_l);_q>=k;_q--){while(l<=r&&q[r].fi+abs(_q-q[r].se)<dp[i-1][_q][j])r--;q[++r]={dp[i-1][_q][j],_q};}dp[i][k][j]=q[l].fi+abs(k-q[l].se);}}} 		}/*cout<<"cur->"<<i<<endl;for(int xi=1;xi<=n;xi++){for(int j=1;j<=m;j++){cout<<xi<<' '<<j<<' '<<dp[i][xi][j]<<endl;}}*/}int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){ans=max(ans,dp[ka][i][j]);}}cout<<ans<<'\n';return 0;
}

loj10183
dp i j 表示 第i天手里有j个股票的最大可能

暴力dp就是

for(int i=1;i<=n;i++){for(int j=0;j<=mx;j++){int buy=min(j,as[i]);for(int k=0;k<=buy;k++){for(int x=0;x<=max(0,i-w-1);x++){dp[i][j]=max(dp[i][j],dp[x][j-k]-k*ap[i]);}}int cell=min(mx-j,bs[i]);for(int k=0;k<=cell;k++){for(int x=0;x<=max(0,i-w-1);x++){dp[i][j]=max(dp[i][j],dp[x][j+k]+k*bp[i]);}}}
}

然后发现 最内层可以记录一下前缀最大值。

for(int i=1;i<=n;i++){for(int j=0;j<=mx;j++){int buy=min(j,as[i]);for(int k=0;k<=buy;k++){dp[i][j]=max(dp[i][j],pr[j-k]-k*ap[i]);}int cell=min(mx-j,bs[i]);for(int k=0;k<=cell;k++){dp[i][j]=max(dp[i][j],pr[j+k]+k*bp[i]);}}
}

对买和卖分开考虑。

然后就可以 维护一个单调队列。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define wzh(x) cerr<<#x<<' '<<x<<endl
LL dp[2002][2002];
LL as[N],bs[N],ap[N],bp[N],t,mx,w;
LL pr[N],su[N],ans=-1e18;
pair<LL,int>q[N],p[N];
const LL inf=1e18;
int main() {ios::sync_with_stdio(false);cin>>t>>mx>>w;for(int i=1;i<=t;i++)cin>>ap[i]>>bp[i]>>as[i]>>bs[i];for(int i=0;i<=mx;i++)pr[i]=-inf;for(int i=0;i<=t;i++){for(int j=0;j<=mx;j++){dp[i][j]=-inf;}}dp[0][0]=0;pr[0]=0;for(int i=1;i<=t;i++){int l=1,r=0;int dl=1,dr=0;if(i-w-1>=0)for(int j=0;j<=mx;j++)pr[j]=max(pr[j],dp[i-w-1][j]);if(i<=w){for(int j=0;j<=as[i];j++)dp[i][j]=max(dp[i][j],-j*ap[i]);continue;}for(int j=0;j<=mx;j++){LL buy=min(1ll*j,as[i]);// 全 买 或 卖 // find maxinum pre[j-x]-x*ap[i] x in [0,buy]// j-x in [j-buy,j]int _l=max(0ll,j-buy);while(l<=r&&q[l].se<_l)l++;// 在范围之外的while(l<=r&&pr[j]>q[r].fi-1ll*ap[i]*abs(j-q[r].se))r--;//在范围内 但是 不优的 q[++r]={pr[j],j};//当前的if(l<=r){dp[i][j]=q[l].fi-1ll*ap[i]*abs(j-q[l].se);}ans=max(ans,dp[i][j]);}for(int j=mx;j>=0;j--){int cell=min(mx-j,bs[i]);//dp[i][j] find maxinum pr[j+k]+1ll*k*bp[i];//j+k in [j,j+cell]int _r=min(mx,0ll+j+cell);while(dl<=dr&&p[dl].se>_r)dl++;while(dl<=dr&&pr[j]>p[dr].fi+1ll*bp[i]*abs(p[dr].se-j))dr--;p[++dr]={pr[j],j};        if(dl<=dr)dp[i][j]=max(dp[i][j],p[dl].fi+1ll*bp[i]*abs(p[dl].se-j));ans=max(ans,dp[i][j]);}}cout<<ans<<'\n';return 0;
}