洛谷题库 P2569 [SCOI2010]股票交易 简略题解

洛谷题库 P2569 [SCOI2010]股票交易

设 $f(i,j,0/1/2)$ 表示第 $i$ 天持有 $j$ 支股票，并且当天进行了 持有 / 买 / 卖 操作，所能获得的最大的收益。很容易想到以下转移：

$$\begin{aligned}&f(i,j,0) = \max \{f(k,j,t) \mid k < i,t\in\{0,1,2\}\}; \\
&f(i,j,1)= \max \{f(k,p,t) \mid k < i-w, p \leq j,t\in\{0,1,2\}\}; \\
&f(i,j,2)= \max \{f(k,p,t) \mid k < i-w, p \geq j,t\in\{0,1,2\}\} \end{aligned}$$

观察发现第三维度是没有意义的——每一次转移的时候对于前序状态都使用了第三维的全部子状态。所以我们直接压缩掉。

另外，还有一个优化：易知 $f(i-1,j)$ 已经包含了 $\max \{f(k-1,j)\}$ 等所有最优决策，所以我们不用到 $w$ 天前再选一遍。

于是有优化后的转移：

$$f(i,j) = \max \begin{cases} f(i-1,j); \\
f(i-w-1,p)-\text{ap}_i \times (j-p), (p \geq 0 \land j-p \geq \text{as}_i); \\
f(i-w-1,g)+ \text{bp}_i \times (g-j), (g \leq p \land g-j \leq \text{bs}_i); \end{cases}$$

易知当 $j$ 确定时，$\text{ap}_j\times j$为定值。又因为题目中有$\text{as, bs}$的限制，所以可以在顺推转移时将决策看作一个“滑动窗口”。

我们希望在$p$合法的情况下，$f(i-w-1,p)+ \text{ap}_i \times p$ 最大，$f(i-w-1,g) +\text{bp}_i \times g$ 最大。很明显，决策具有单调性。单调队列优化已箭在弦上。对于上述两种转移，可以分别通过$j$从小到大、从大到小扫描，即时加入当前决策、删除超限决策即可。

最终算法的时间复杂度为$\mathrm{O}(N^2)$。

R54178287 记录详情

#include <bits/stdc++.h>
using namespace std;

const int N = 2048; 
int  n, max_p, w;
int ap[N], bp[N], as[N], bs[N];
int dp[N][N], q[N], h, t, dat[N], ans, pos;

int main () {
	/* 洛谷题库 P2569 [SCOI2010]股票交易 */
	scanf ("%d%d%d", &n, &max_p, &w);
	for (int i = 1; i <= n; ++i)
		scanf ("%d%d%d%d", ap + i, bp + i, as + i, bs + i); 
	
	memset (dp, -0x3f, sizeof dp);
	dp[0][0] = 0; 
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= max_p; ++j)
			dp[i][j] = dp[i - 1][j];
		pos = max (0, i - w - 1); 
		// 今天卖了股票
		if (pos == 0) goto SELL;
		h = t = 0; memset (dat, 0, sizeof dat); memset (q, 0, sizeof q);
		for (int j = max_p; j >= 0; --j) {
			// 维护决策的单调队列
			dat[j] = dp[pos][j] + bp[i] * j; // 新的决策！ 
			while (h < t && q[h + 1] > j + bs[i]) ++h; // 删除超界决策
			while (h < t && dat[q[t]] <= dat[j]) --t;
			q[++t] = j;
			dp[i][j] = max (-bp[i] * j + dat[q[h + 1]], dp[i][j]), ans = max (ans, dp[i][j]);
		}
		// 今天买了股票
		SELL: h = t = 0; memset (dat, 0, sizeof dat); memset (q, 0, sizeof q);
		for (int j = 0; j <= max_p; ++j) {
			dat[j] = dp[pos][j] + ap[i] * j;
			while (h < t && q[h + 1] < j - as[i]) ++h;
			while (h < t && dat[q[t]] <= dat[j]) --t;
			q[++t] = j;
			dp[i][j] = max (-ap[i] * j + dat[q[h + 1]], dp[i][j]), ans = max (ans, dp[i][j]);
		}
	}
	
	printf ("%d", ans);

	return 0;
}

R54178287 记录详情