HDU3401 – Trade(单调队列优化DP)

题目链接：HDU3401

【题意】某人预测未来 T 天的股票交易。在第 i 天，你可以用 APi 元买入一股股票，也可以卖出一股股票收入 BPi 元。

另外还有一些限制。第 i 天最多只能买入 ASi 股股票，也最多只卖出 BSi 股的股票。两次交
易的时间必须相隔 W 天。即如果第 i 天作了交易，下一次交易必须在 i+W+1 天及以后。而
且，任何时候只能最多持有 MaxP 数量的股票。在第一个交易日之前，假如你有足够多的钱，但没有股票。
现在问题是：经过 T 个交易日后，最多可以赚多少钱？

【分析】首先可以推出DP方程：

ans = max{dp[i-1][j], dp[i-w-1][k]+(j-k)*ap[i] (j-k <= as[i]), dp[i-w-1][k]+(k-j)*bp[i] (k-j <= bs[i])}

分别代表没有任何操作，买入k股和卖出k股。因为可以不做任何操作，所以不需要枚举哪一天，i-w-1就是最优值了，但是这样要枚举k，复杂度是T*MAXP^2的，肯定超时，还需要继续优化。以买入为例，变形一下DP方程为dp[i][j] = max{dp[i-w-1][k]-k*ap[i]} – j*ap[i];这样可以用一个单调队列存两个值k和{dp[i-w-1][k]-k*ap[i]} ，保证他们单调(其实就是保证存以前出现过的)的；同理卖出也用单调队列维护，就可以把复杂度降为T*MAXP。

【AC CODE】296ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 2000+10;
struct Q{
	int k,v;
}q[MAXN];
int front,rear,ap[MAXN],bp[MAXN],as[MAXN],bs[MAXN], dp[MAXN][MAXN];
//dp[i][j]第i天持有j股时的最多赚多少钱

int main()
{
#ifdef SHY
	freopen("e:\\1.txt", "r", stdin);
#endif
	int t;
	scanf("%d%*c", &t);
	while(t--)
	{
		int n,mp,w;
		scanf("%d %d %d%*c", &n, &mp, &w);
		repe(i,1,n) scanf("%d %d %d %d%*c", &ap[i], &bp[i], &as[i], &bs[i]);
		clc(dp,-0x3f);
		repe(i,1,w+1)
		{
			int now = min(mp,as[i]);
			repe(j,0,now) dp[i][j] = -(j*ap[i]);
		}
		repe(i,1,n)
		{
			repe(j,0,mp)
				dp[i][j] = max(dp[i][j],dp[i-1][j]);
			if(i <= w+1) continue;
			//单调队列只维护i-w-1天的max值, k是pos值，v是维护的值
			front = 1, rear = 0;
			repe(j,0,mp)
			{
				int now = dp[i-w-1][j]+j*ap[i];
				while(front <= rear && now > q[rear].v) rear--;//入队
				q[++rear].k = j, q[rear].v = now;
				//根据限制条件删掉队首无用的值,因为在这里as[i]是个定值
				while(front <= rear && j > q[front].k+as[i]) front++;
				dp[i][j] = max(dp[i][j], q[front].v-j*ap[i]);
			}
			front = 1, rear = 0;
			per(j,mp,0) //j >= k(由k股卖出变成j) 所以需要j从大到小枚举才能保证k已经计算过
			{
				int now = dp[i-w-1][j]+j*bp[i];
				while(front <= rear && now > q[rear].v) rear--;
				q[++rear].k = j, q[rear].v = now;
				while(front <= rear && j < q[front].k-bs[i]) front++;
				dp[i][j] = max(dp[i][j], q[front].v-j*bp[i]);
			}
		}
		int ans = -INF;
		repe(j,0,mp) ans = max(ans,dp[n][j]);
		printf("%d\n", ans);
	}
	return 0;
}