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

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

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

f(i,j,0)=max{f(k,j,t)k<i,t{0,1,2}};f(i,j,1)=max{f(k,p,t)k<iw,pj,t{0,1,2}};f(i,j,2)=max{f(k,p,t)k<iw,pj,t{0,1,2}}\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(i1,j)f(i-1,j) 已经包含了 max{f(k1,j)}\max \{f(k-1,j)\} 等所有最优决策,所以我们不用到 ww 天前再选一遍。

于是有优化后的转移:

f(i,j)=max{f(i1,j);f(iw1,p)api×(jp),(p0jpasi);f(iw1,g)+bpi×(gj),(gpgjbsi);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}

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

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

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

R54178287 记录详情

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
#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 记录详情

  • 2021年7月25日