P2569 [SCOI2010] 股票交易 题解

P2569 [SCOI2010] 股票交易

搬运工
稍微复杂一点的单调队列优化DP
直接设 \(f_{i\ j}\) 表示在第 \(i\) 天，手上还剩 \(j\) 个股票时的最大收入。
容易写出状态转移方程：\(f_{i\ j}=max\{f_{k\ t}+(t-j)\cdot w\}\)，这样不好看，我们可以拆成这样的形式：

这样 \(max\) 里面的东西与 \(i\) 和 \(j\) 无关，显然单调队列优化。
这里的 \(k,t,w\) 都有限定，\(k\le i-len+1\qquad j-as_i\le t\le j+bs_i\)，\(w\) 的取值取决于这个状态是买入转移过来的还是卖出转移过来的。
我们发现 \(f_{k\ t}\) 的取值范围实际上是一个只有长不断伸缩而宽递增的一个矩形（以 \(i\) 为宽，以 \(j\) 为长）。
这样就很优，因为这样我们纵向的最值随便维护，横向的直接那单调队列。（一开始我还以为是理想的正方形）
直接转移还是不行的，因为这样相当于每天只进行一次买或卖的转移，但是买和卖能够同时转移。
我们考虑开一个辅助数组 \(zc\)，现将某天卖股票的转移放入 \(zc\)，在考虑从 \(zc\) 由买股票的转移放入 \(f\) 数组，先转移卖可以确保不会超出股票数目最大限制。
\(DP\) 结束后，我们找后 \(W+1\) 天的剩余 \(0\) 股票时的最值就好。

#include<bits/stdc++.h>
inline int read(){
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
const int N=2005;
int T,MaxP,W,AP[N],BP[N],AS[N],BS[N],headl=1,taill=0,headr=1,tailr=0,f[N][N],ql[N],qr[N],zc[N],maxq[N];
int main(){
	// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
	T=read(),MaxP=read(),W=read();
	memset(f,-0x3f,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<=T;++i)
		AP[i]=read(),BP[i]=read(),AS[i]=read(),BS[i]=read();
	for(int i=1;i<=T;++i){
		headl=headr=1,taill=tailr=0;
		int ri=std::max(0,i-W-1);
		for(int j=0;j<=MaxP;++j)
			if(f[ri][j]>=f[maxq[j]][j])maxq[j]=ri;
		for(int j=0;j<=std::min(BS[i],MaxP);++j){
			while(headr<=tailr&&f[maxq[j]][j]+j*BP[i]>=f[maxq[qr[tailr]]][qr[tailr]]+qr[tailr]*BP[i])tailr--;
			qr[++tailr]=j;
		}
		for(int j=0;j<=MaxP;++j){
			int r=std::min(MaxP,j+BS[i]);
			while(headr<=tailr&&f[maxq[r]][r]+r*BP[i]>=f[maxq[qr[tailr]]][qr[tailr]]+qr[tailr]*BP[i])tailr--;
			qr[++tailr]=r;
			if(qr[headr]<j)headr++;
			zc[j]=f[maxq[qr[headr]]][qr[headr]]+(qr[headr]-j)*BP[i];
		}
		for(int j=0;j<=MaxP;++j){
			int l=std::max(0,j-AS[i]);
			while(headl<=taill&&zc[j]+j*AP[i]>=zc[ql[taill]]+ql[taill]*AP[i])taill--;
			ql[++taill]=j;
			if(ql[headl]<l)headl++;
			f[i][j]=zc[ql[headl]]-(j-ql[headl])*AP[i];
		}
	}
	int ans=0;
	for(int i=T-W;i<=T;++i)ans=std::max(f[i][0],ans);
	std::cout<<ans<<'\n';
}