P2569 [SCOI2010]股票交易 题解

设 \(f_{i,j}\) 表示第 1 天至第 \(i\) 天，手上有 \(j\) 股股票时拥有的最多钱。

考虑转移，首先就有 \(f_{i,j}=-j\times ap_i\) 即单纯买入，然后由转移方程定义有 \(f_{i,j}=\max\{f_{i,j},f_{i-1,j}\}\)，就是不买入不卖出。

现在考虑会买入卖出的情况，由于题中规定交易至少间隔 \(w\) 天，因此能追溯的最优解一定在 \(f_{i-w-1,k}\)，枚举第二维 \(k\) 有 \(f_{i,j}=\max\{f_{i-w-1,k}-(j-k)\times ap_i\mid j-as_i\le k\le j\}\)，\(k\le j\) 的等号严格意义上应该不取，但是显然取了也不会影响转移方程正确性。

同理，卖出情况有 \(f_{i,j}=\max\{f_{i-w-1,k}+(k-j)\times bp_i\mid j\le k\le j+bs_i\}\)。

注意到我们需要枚举 \(i,j\)，然后这个式子是关于 \(f_{i-w-1,k}\) 的一个不存在 \(j\times k\) 的线性表达式，满足单调队列优化条件，优化即可。

Code：

/*
========= Plozia =========
	Author:Plozia
	Problem:P2569 [SCOI2010]股票交易
	Date:2022/9/26
========= Plozia =========
*/

#include <bits/stdc++.h>
typedef long long LL;
using std::deque;

const int MAXN = 2e3 + 5;
int n, m, w;
LL f[MAXN][MAXN], as[MAXN], bs[MAXN], ap[MAXN], bp[MAXN];

int Read()
{
	int sum = 0, fh = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
	return sum * fh;
}

int main()
{
	n = Read(), m = Read(); w = Read(); memset(f, -0x7f, sizeof(f));
	for (int i = 1; i <= n; ++i) ap[i] = Read(), bp[i] = Read(), as[i] = Read(), bs[i] = Read();
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 0; j <= as[i]; ++j) f[i][j] = -j * ap[i];
		for (int j = 0; j <= m; ++j) f[i][j] = std::max(f[i - 1][j], f[i][j]);
		if (i - w - 1 <= 0) continue ;
		deque <int> q;
		for (int j = 0; j <= m; ++j)
		{
			while (!q.empty() && q.front() < j - as[i]) q.pop_front();
			while (!q.empty() && f[i - w - 1][q.back()] - (j - q.back()) * ap[i] <= f[i - w - 1][j]) q.pop_back();
			q.push_back(j); f[i][j] = std::max(f[i][j], f[i - w - 1][q.front()] - (j - q.front()) * ap[i]);
		}
		q.clear();
		for (int j = m; j >= 0; --j)
		{
			while (!q.empty() && q.front() > j + bs[i]) q.pop_front();
			while (!q.empty() && f[i - w - 1][q.back()] + (q.back() - j) * bp[i] <= f[i - w - 1][j]) q.pop_back();
			q.push_back(j); f[i][j] = std::max(f[i][j], f[i - w - 1][q.front()] + (q.front() - j) * bp[i]);
		}
	}
	LL ans = 0;
	for (int j = 0; j <= m; ++j) ans = std::max(ans, f[n][j]);
	printf("%lld\n", ans); return 0;
}