本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15905849.html

题目链接

题目

最近 lxhgww\text{lxhgww} 又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。

通过一段时间的观察，lxhgww\text{lxhgww} 预测到了未来 TT 天内某只股票的走势，第 ii 天的股票买入价为每股 APiAP_i，第 ii 天的股票卖出价为每股 BPiBP_i（数据保证对于每个 ii，都有 APi≥BPiAP_i \geq BP_i），但是每天不能无限制地交易，于是股票交易所规定第 ii 天的一次买入至多只能购买 ASiAS_i 股，一次卖出至多只能卖出 BSiBS_i 股。

另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔 WW 天，也就是说如果在第 ii 天发生了交易，那么从第 i+1i+1 天到第 i+Wi+W 天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过 MaxP\text{MaxP}。

在第 11 天之前，lxhgww\text{lxhgww} 手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，TT 天以后，lxhgww\text{lxhgww} 想要赚到最多的钱，聪明的程序员们，你们能帮助他吗？

思路

明显的dp。

设 dp[i][j]dp[i][j] 表示第 ii 天持股为 jj 的最大钱数，首先可以从上一天或者第0天推导过来。

然后考虑买入的情况，由于我们每次由上一天推导过来，具有传递性，所以我们可以由第 i−w−1i-w-1 天推导过来。

假设第 i−w−1i-w-1 天持股数量为 kk，那么需满足 j−asi⩽k⩽j−1j-as_i\leqslant k\leqslant j-1，转移为：

dp[i][j]=dp[i−w−1][k]−(j−k)×apidp[i][j]=dp[i-w-1][k]-(j-k)\times ap_i

可是这样的时间复杂度达到三次方级别，于是我们对上面的式子变换一下：

dp[i][j]=(dp[i−w−1][k]+k×api)−j×apidp[i][j]=(dp[i-w-1][k]+k\times ap_i)-j\times ap_i

明显，前面那一部分可以用单调队列优化。

卖出情况同理。

总结

这是一道非常经典的dp加单调队列优化。

dp方面，传递性的思想很巧妙。

有些时候，dp式子需要进行一定变换才能使用单调队列优化。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// Problem: P2569 [SCOI2010]股票交易
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2569
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define mo
#define N 2010
//#define M
int n, m, i, j, k; 
int ap[N], bp[N], as[N], bs[N]; 
int dp[N][N], ans, w, mx; 
pair<int, int>p; 
deque<pair<int, int > >q1, q2; 

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	memset(dp, 0x80, sizeof(dp)); 
	n=read(); m=read(); w=read(); 
	for(i=1; i<=n; ++i)
	{
		ap[i]=read(); bp[i]=read(); 
		as[i]=read(); bs[i]=read(); 
	}
	for(i=1; i<=n; ++i)
	{
		for(j=0; j<=m; ++j)
		{
			dp[i][j]=dp[i-1][j]; 
			if(j<=as[i]) dp[i][j]=max(dp[i][j], -j*ap[i]); 
		}
		if(i<=w) continue; 
		for(j=0; j<=m; ++j)
		{
			while(!q1.empty() && q1.front().second<j-as[i]) q1.pop_front(); 
			while(!q1.empty() && q1.back().first<=dp[i-w-1][j-1]+(j-1)*ap[i]) q1.pop_back(); 
			p.first=dp[i-w-1][j-1]+(j-1)*ap[i]; p.second=j-1; q1.push_back(p); 
			dp[i][j]=max(dp[i][j], q1.front().first-j*ap[i]); 
		}
		for(j=m; j>=0; --j)
		{
			while(!q2.empty() && q2.front().second>j+bs[i]) q2.pop_front(); 
			while(!q2.empty() && q2.back().first<=dp[i-w-1][j+1]+(j+1)*bp[i]) q2.pop_back(); 
			p.first=dp[i-w-1][j+1]+(j+1)*bp[i]; p.second=j+1; q2.push_back(p); 
			dp[i][j]=max(dp[i][j], q2.front().first-j*bp[i]); 
		}
		q1.clear(); q2.clear(); 
	}
	for(i=0; i<=m; ++i) ans=max(ans, dp[n][i]); 
	printf("%lld", ans); 
	return 0;
}