[SCOI2010]股票交易

XX.[SCOI2010]股票交易

这题状态很好想：设\(f[i][j]\)表示：第\(i\)天，持有\(j\)支股票，的最大收益。

然后我就脑残了，想了个\(O(n^2m^2)\)的弱智初始DP，然后就WA掉惹。

实际上转移也挺简单的。设第\(i\)天买股票花\(a_i\)元，卖股票花\(b_i\)元，可以买\(A_i\)次，卖\(B_i\)次。

1. 从起始状态转移。即，如果有\(j\leq A_i\)，\(f[i][j]=-j*a_i\)。

2. 这一时刻不买。即，\(f[i][j]=f[i-1][j]\)。

3. 从\(i-w-1\)时刻买。即，\(f[i][j]=\max\{f[i-w-1][l]+\text{买或卖的费用}\}\)

然后1和2都是\(nm\)的；3套上单调队列也是\(nm\)的；总复杂度\(O(nm)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,w,a[2010],b[2010],A[2010],B[2010];
ll f[2010][2010];
deque<int>q;
int main(){
	scanf("%d%d%d",&n,&m,&w),w++,memset(f,0x80,sizeof(f));
	for(int i=1;i<=n;i++)scanf("%d%d%d%d",&a[i],&b[i],&A[i],&B[i]);
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(j<=A[i])f[i][j]=-j*a[i];
			f[i][j]=max(f[i][j],f[i-1][j]);	
		}
		if(i-w<=0)continue;
		int k=i-w;
		q.clear();
		for(int j=0;j<=m;j++){
			while(!q.empty()&&j-q.front()>A[i])q.pop_front();
			while(!q.empty()&&f[k][q.back()]-(j-q.back())*a[i]<=f[k][j])q.pop_back();
			q.push_back(j);
			f[i][j]=max(f[i][j],f[k][q.front()]-(j-q.front())*a[i]);
		}
		q.clear();
		for(int j=m;j>=0;j--){
			while(!q.empty()&&q.front()-j>B[i])q.pop_front();
			while(!q.empty()&&f[k][q.back()]+(q.back()-j)*b[i]<=f[k][j])q.pop_back();
			q.push_back(j);
			f[i][j]=max(f[i][j],f[k][q.front()]+(q.front()-j)*b[i]);
		}
	}
//	for(int i=1;i<=n;i++){for(int j=0;j<=m;j++)printf("%d ",f[i][j]);puts("");}
	printf("%lld\n",f[n][0]);
	return 0;
}