#C241016B. [SCOI2010] 股票交易

标签（Label）

动态规划
单调队列
推式子

前言（Front talk）

$\qquad$这道题主要在枚举上比较艰难，其实也是我没有仔细分类的问题，要想清楚初始状态，转移，勤加练习。

$\qquad$这道题基本上是我看一点提示推后面，推不动了又看提示，所以非常的清楚自己在那些地方没有想到。

网址（Website）

P2569 [SCOI2010] 股票交易 - 洛谷

「SCOI2010」股票交易 - Super

题解（Solution）

看到 $n$ 的范围，直接想到动态规划，设 $f_{i,j}$ 表示到了第 $i$ 天，当前持有 $j$ 张票。

然后我就卡住了，状态转移方程怎么推呢？我甚至不知道如何分类讨论。惊讶地发现每天不能同时买和卖之后，我开始枚举：

分 $4$ 种情况：

前面一直没有买，这次直接买入： $f_{i,j} = -ap_i\times j$；
这一天啥都不干：$f_{i,j} = \max(f_{i,j}, f_{i-1,j})$；
已经买了，现在继续买：$f_{i,j}=\max(f_{i,j},\ f_{i-w-1,j-k}-ap_i\times k)$ ，$k\in[1,as]$ ；
把手持的股票卖出：$f_{i,j}=\max(f_{i,j}, \ f_{i-w-1,j+k}+bp_i\times k)$ ， $k\in[1,bs]$ 。

然后我惊讶地发现公式里面对 $k$ 的限制很像单调栈！！！

结果怎么推都推不出来。。。

看了题解之后，发现题解里面是这样写的：

分 $4$ 种情况：

前面一直没有买，这次直接买入：$f_{i,j} = -ap_i\times j$；
这一天啥都不干：$f_{i,j} = \max(f_{i,j}, f_{i-1,j})$；
已经买了，现在继续买：$f_{i,j}=\max(f_{i,j},\ f_{i-w-1,k}-ap_i\times (j-k))$ ，$k\in[j-as,j-1]$；
把手持的股票卖出：$f_{i,j}=\max(f_{i,j}, \ f_{i-w-1,k}+bp_i\times (k-j)$ ， $k\in[j+1,j+bs]$ 。

状态转移就只有些许的区别，但是实际上我的那种就是推不出来。

总结一个方法：状态转移的时候尽量把简单的量（或常数量）放到状态里面，把复杂的量放到状态外面。

然后就可以轻松的推式子了，这里只考虑买进，卖出的式子类比即可：

$f_{i,j}=\max(f_{i,j},\ f_{i-w-1,k}-ap_i\times (j-k))\\\quad\ =\max(f_{i,j},\ f_{i-w-1,k}-ap_i\times j+ap_i\times k)\\\quad\ =\max(f_{i,j},\ f_{i-w-1,k}+ap_i\times k)-ap_i\times j$

然后我们就发现，可以每次把 $f_{i-w-1,k}+ap_i\times k$ 放到单调栈里面维护，同时保证 $k\in[j-as, j-1]$ 即可。

时间复杂度 $O(n^2)$ 。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int N = 5005;
bool ST;

int f[N][N],q[N];
int n,m,w,ans;

void solve(){
	n = rd(), m = rd(), w = rd();
	memset(f, -0x3f, sizeof f);
	For(i,1,n){	
		int ap=rd(), bp=rd(), as=rd(), bs=rd();
		For(j,0,as) f[i][j] = -ap*j;//重新开始买
		For(j,0,m) f[i][j] = max(f[i-1][j], f[i][j]);//什么都不买
		
		if(i<=w) continue;
		
		int l = 1, r = 0;
		For(j,0,m){//维护单调队列的时候，如果已经存储了值，那么可以只记录下标，在保证单调性的时候在计算就好了
			while(l<=r && q[l] < j-as) l++;
			while(l<=r && f[i-w-1][q[r]]+q[r]*ap <= f[i-w-1][j]+j*ap) r--;
			q[++r] = j;
			if(l<=r) f[i][j] = max(f[i-w-1][q[l]]+q[l]*ap-j*ap, f[i][j]);
		}
		
		l = 1, r = 0;
		Rof(j,m,0){
			while(l<=r && q[l] > j+bs) l++;
			while(l<=r && f[i-w-1][q[r]]+q[r]*bp <= f[i-w-1][j]+j*bp) r--;
			q[++r] = j;
			if(l<=r) f[i][j] = max(f[i-w-1][q[l]]+q[l]*bp-j*bp, f[i][j]);
		}
	}
	For(j,0,m) ans = max(ans, f[n][j]);
	printf("%d\n",ans);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1, Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}