「SCOI2010」股票交易 - 背包 DP + 单调队列

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

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

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

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

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

\(0\leq W<T\leq 2000,1\leq\text{MaxP}\leq2000,1\leq BP_i\leq AP_i\leq 1000,1\leq AS_i,BS_i\leq\text{MaxP}\)

解题思路

本题可通过背包 DP 解决。

显然我们可以定义状态 \(f_{i, j}\)，表示在第 \(i\) 天有 \(j\) 张股票所拥有的最多钱数。

于是我们可以有下列 \(3\) 中情况：

  1. 不买不卖：\(f_{i, j} = \max\{f_{i, j}, f_{i - 1, j}\}\)
  2. 买股票：\(f_{i, j} = \max\{f_{i, j}, f_{i - w - 1, k} + \text{ap}_i * (k - j)\} \quad k \in [j - \text{as}_i, j)\)
  3. 卖股票：\(f_{i, j} = \max\{f_{i, j}, f_{i - w - 1, k} + \text{bp}_i * (k - j)\} \quad k \in (j, j + \text{bs}_i]\)

初始状态为下列两种：

  1. 直接买：\(f_{i, j} = -\text{ap}_i \times j \quad j \in [0, \text{as}_i]\)
  2. 不买：除直接买外情况外 \(f_{i, j} = -\infty\)

但直接进行 DP 时间复杂度为 \(O(n^3)\)，肯定无法通过本题。

观察状态转移方程，我们可以发现该方程可用单调队列优化。

对于状态转移方程：

\[ f_{i, j} = \max \begin{cases} f_{i - 1, j} \\ \max\{f_{i - w - 1, k} + \text{ap}_i * (k - j)\} & k \in [j - \text{as}_i, j) \\ \max\{f_{i - w - 1, k} + \text{bp}_i * (k - j)\} & k \in (j, j + \text{bs}_i] \end{cases} \]

通过简单代数变化可转化为：

\[ f_{i, j} = \max \begin{cases} f_{i - 1, j} \\ \max\{f_{i - w - 1, k} + \text{ap}_i * k\} - \text{ap}_i * j & k \in [j - \text{as}_i, j) \\ \max\{f_{i - w - 1, k} + \text{bp}_i * k\} - \text{bp}_i * j & k \in (j, j + \text{bs}_i] \end{cases} \]

由于 \(\max\{f_{i - w - 1, k} + \text{ap}_i * k\}\) 和 \(\max\{f_{i - w - 1, k} + \text{bp}_i * k\}\) 与 \(j\) 无关，故对于任何 \(j\)，该式解出的值相等。于是我们可以用单调队列预处理该式。优化掉 \(k\) 这个维度，于是将复杂度优化到 \(O(n^2)\)。

代码演示

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
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int MAXN = 2000, INF = 0x3f3f3f3f;

template <typename T>
struct MonotoneQueue {
    std::deque<T> q, m;

    void push(const T &x) {
        q.push_back(x);
        while (!m.empty() && m.back() < x) m.pop_back();
        m.push_back(x);
    }

    void pop() {
        T x = q.front();
        q.pop_front();
        if (x == m.front()) m.pop_front();
    }

    bool empty() {
        return m.empty();
    }

    T top() {
        return m.front();
    }
};

int main() {
    int t, maxp, w;
    static int ap[MAXN + 1], bp[MAXN + 1], as[MAXN + 1], bs[MAXN + 1];

    scanf("%d %d %d", &t, &maxp, &w);
    for (int i = 1; i <= t; i++) {
        scanf("%d %d %d %d", &ap[i], &bp[i], &as[i], &bs[i]);
    }

    static int f[MAXN + 1][MAXN + 1];
    memset(f, 0xcf, sizeof(f));

    for (int i = 1; i <= t; i++) {
        for (int j = 0; j <= as[i]; j++) f[i][j] = -ap[i] * j;
        for (int j = 0; j <= maxp; j++) f[i][j] = std::max(f[i][j], f[i - 1][j]);

        MonotoneQueue< std::pair<int, int> > buy, sell;
        while (!buy.empty()) buy.pop();
        while (!sell.empty()) sell.pop();

        if (i - w - 1 >= 0) {
            for (int j = 0; j <= maxp; j++) {
                while (!buy.empty() && buy.top().second < j - as[i]) buy.pop();
                buy.push( std::make_pair(f[i - w - 1][j] + j * ap[i], j) );
                f[i][j] = std::max(f[i][j], buy.top().first - j * ap[i]);
            }

            for (int j = maxp; j >= 0; j--) {
                while (!sell.empty() && sell.top().second > j + bs[i]) sell.pop();
                sell.push( std::make_pair(f[i - w - 1][j] + j * bp[i], j) );
                f[i][j] = std::max(f[i][j], sell.top().first - j * bp[i]);
            }
        }
    }

    int ans = -INF;
    for (int i = 0; i <= maxp; i++) ans = std::max(ans, f[t][i]);

    printf("%d\n", ans);

    return 0;
}