单调队列优化dp
你说得对，但是单调队列优化 dp 我都是用线段树写的。
绝对不是因为不会写
情景
对于一类 dp 的状态转移方程是类似于 \(f_i=\max\{f_j\}(j\in[l,r])\) 的优化。
然而实际题目中很难凑得这么正好，常见的是 \(f_i=\max\{f_j+a\}+b\) 之类的。
一般来说，dp 的 \(i\) 这一维是一个个递增的，如果 \(j\) 取值的区间 \([l,r]\) 也是逐渐扩大的，那么就可以用单调队列搞。类似于莫队。
单调队列怎么写我之前写过，翻翻我的 blog 就找的到了。
但是这种优化 dp 思想简单，所以看例题。
例题
T1 琪露诺
- link
先感叹一下：这题是我老师 24 年 1 月推给我们做的，但是我现在 26 年 1 月才捡起来，唉……
状态：设 \(f_i\) 表示走到第 \(i\) 号格子的最大冰冻指数。
方程：\(f_i=\max\{f_j\}+a_i\mid j\in[i-r,i-l]\)。
算是简单的一种吧。
注意到枚举到 \(i\) 的时候，\(i-1\) 的答案是算好了的，所以只需要添加 \(i\) 号位的答案进去。
那么我们可以用单调队列，维护 \([i-r,i-l]\) 的最大的 \(f\) 值。
不过毕竟我很懒，直接线段树搞定。代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
#define FUP(i,x,y) for(auto (i)=(x);(i)<=(y);++(i))
#define FDW(i,x,y) for(auto (i)=(x);(i)>=(y);--(i))
inline void Rd(auto &num);
const int N=2e5+5;
const ljl inf=1e18;
int n,l,r;
ljl a[N],f[N],ans=-inf;
struct NODE{int l,r;ljl maxn;
}node[N*4];
#define lc (p<<1)
#define rc (p<<1|1)
void pushup(int p)
{if(node[p].l==node[p].r)return;node[p].maxn=max(node[lc].maxn,node[rc].maxn);return;
}
void bld(int l,int r,int p)
{node[p].l=l;node[p].r=r;if(l==r)return;int mid=(l+r)/2;bld(l,mid,lc);bld(mid+1,r,rc);return;
}
ljl query(int l,int r,int p)
{if(l<0||r<0||r<l)return -inf;if(l<=node[p].l&&node[p].r<=r)return node[p].maxn;int mid=(node[p].l+node[p].r)/2;ljl ans=-inf;if(l<=mid)ans=max(ans,query(l,r,lc));if(mid<r)ans=max(ans,query(l,r,rc));return ans;
}
void addx(int x,ljl val,int p)
{if(node[p].l==node[p].r&&node[p].l==x){node[p].maxn=val;return;}int mid=(node[p].l+node[p].r)/2;if(x<=mid)addx(x,val,lc);else addx(x,val,rc);pushup(p);return;
}
int main(){Rd(n);Rd(l);Rd(r);FUP(i,0,n)Rd(a[i]);bld(0,n,1);FUP(i,1,n){ljl tmp=query(max(0,i-r),i-l,1);
// cout<<"----------\n";if(tmp==-inf)f[i]=-inf;else f[i]=tmp+a[i];addx(i,f[i],1);}FUP(i,1,n)if(i+r>n)ans=max(ans,f[i]);
// FUP(i,1,n)cout<<f[i]<<' ';
// cout<<'\n';printf("%lld\n",ans);return 0;
}
inline void Rd(auto &num)
{num=0;char ch=getchar();bool f=0;while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch-'0');ch=getchar();}if(f)num=-num;return;
}
T2 股票交易
- link
哦哦哦怎么是省选真题。
感觉难在设状态和方程，以及优化时的被发现的明亮的眼睛。
设 \(f_{i,j}\) 表示到了第 \(i\) 天，手中有 \(j\) 张牌的最大收益。
方程：
\[f_i=\max\begin{cases}
f_{i-1,j}\\
-ap\times j\\
f_{i-w-1,k}-(j-k)ap\ \ \ (j-as\le k<j)\\
f_{i-w-1,k}+(k-j)bp\ \ \ (j<k\le j+bs)\\
\end{cases}
\]
前两种简单，直接暴力。
对于后两种，注意到 \(i-w-1\) 是固定的，可以维护区间 \([j-as,j-1]\) 和 \([j+1,j+bs]\) 的最大值。
不过还要拆开式子，存在线段树里的是 \(f_{i-w-1,k}+kap\) 和 \(f_{i-w-1,k}+kbp\)。最后减去 \(jap\) 或 \(jbp\) 即可。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
#define FUP(i,x,y) for(auto (i)=(x);(i)<=(y);++(i))
#define FDW(i,x,y) for(auto (i)=(x);(i)>=(y);--(i))
inline void Rd(auto &num);
const int N=2005,P=2005;
const ljl inf=1e18;
ljl f[N][P],ap,bp,as,bs,ans,p,w,n;
struct NODE{int l,r;ljl maxn;
}node[N*4];
#define lc (p<<1)
#define rc (p<<1|1)
void pushup(int p)
{if(node[p].l==node[p].r)return;node[p].maxn=max(node[lc].maxn,node[rc].maxn);return;
}
void bld(int l,int r,int p)
{node[p].l=l;node[p].r=r;if(l==r)return;int mid=(l+r)/2;bld(l,mid,lc);bld(mid+1,r,rc);return;
}
void addx(int x,ljl val,int p)
{if(node[p].l==node[p].r){node[p].maxn=val;return;}int mid=(node[p].l+node[p].r)/2;if(x<=mid)addx(x,val,lc);else addx(x,val,rc);pushup(p);return;
}
ljl query(int l,int r,int p)
{if(l<=node[p].l&&node[p].r<=r)return node[p].maxn;int mid=(node[p].l+node[p].r)/2;ljl ans=-inf;if(l<=mid)ans=max(ans,query(l,r,lc));if(mid<r)ans=max(ans,query(l,r,rc));return ans;
}
signed main(){Rd(n);Rd(p);Rd(w);for(int i=0;i<n;++i)for(int j=0;j<=p;++j)f[i][j]=-inf;f[0][0]=0;bld(0,p,1);for(int i=1;i<=n;++i){Rd(ap);Rd(bp);Rd(as);Rd(bs);for(int j=0;j<=as;++j)f[i][j]=-j*ap;for(int j=0;j<=p;++j)f[i][j]=max(f[i][j],f[i-1][j]);if(i-w<1)continue;FUP(k,0,p)addx(k,f[i-w-1][k]+k*bp,1);FUP(j,0,p)f[i][j]=max(f[i][j],query(j+1,min(p,j+bs),1)-j*bp);FUP(k,0,p)addx(k,f[i-w-1][k]+k*ap,1);FUP(j,0,p)f[i][j]=max(f[i][j],query(max(0ll,j-as),max(0ll,j-1ll),1)-j*ap);}FUP(i,0,p)ans=max(ans,f[n][i]);printf("%lld\n",ans);return 0;
}
inline void Rd(auto &num)
{num=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch-'0');ch=getchar();}return;
}
衷心警告
能用单调队列别用线段树！！！！
比如例二，时限一秒对吧，我过了对吧，注意看用时。
