「SCOI2010」股票交易

#题面

#题目描述

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

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

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

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

#输入格式

输入数据第一行包括 $3$ 个整数，分别是 $T$，$\mathit{MaxP}$，$W$。

接下来 $T$ 行，第 $i$ 行代表第 $i-1$ 天的股票走势，每行 $4$ 个整数，分别表示 $\mathit{AP}_i, \mathit{BP}_i, \mathit{AS}_i, \mathit{BS}_i$。

#输出格式

输出数据为一行，包括 $1$ 个数字，表示 lxhgww 能赚到的最多的钱数。

#输入输出样例

样例输入 #1

5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1

样例输出 #1

3

#提示

• 对于 $30\%$ 的数据，$0 \leq W < T \leq 50$，$1 \leq \mathit{MaxP}\leq 50$；
• 对于 $50\%$ 的数据，$0 \leq W < T \leq 2000$，$1 \leq \mathit{MaxP} \leq 50$；
• 对于 $100\%$ 的数据，$0 \leq W < T \leq 2000$，$1 \leq \mathit{MaxP} \leq 2000$，$1 \leq \mathit{BP}_i \leq \mathit{AP}_i \leq 1000$，$1 \leq \mathit{AS}_i, \mathit{BS}_i \leq \mathit{MaxP}$。

#思路

先考虑朴素做法。

对于每一天，有 $4$ 种情况：

1. 不操作。

   此时收益与上一天持平。

   转移方程：$f_{i, j} = f_{i - 1, j}$。

2. 从头开始买入股票。此状态即为初始状态。

   此时收益要扣除买股票的钱，当买 $k$ 张股票时，收益为 $-k \times \mathit{AP}_i$。

   转移方程：$f_{i, j} = -j \times \mathit{AP}_i$。

3. 在前一天的基础上买入股票。

   由于前 $1 \sim i - W - 2$ 天的最优收益已经转移到了 $i - W - 1$ 天上，所以只需要枚举第 $i$ 天买多少张股票，并在第 $i - W - 1$ 天中对应股票数量的收益的基础上扣除相应金额即可。

   转移方程：$f_{i, j} = \max_{k = j - \mathit{AS}_i}^{j - 1}\{f_{i - w - 1, k} - (j - k) \times \mathit{AP}_i\}$。

4. 在前一天的基础上卖出股票。

   枚举第 $i$ 天卖多少张股票，并在第 $i - W - 1$ 天中对应股票数量的收益的基础上增加相应金额即可。

   转移方程：$f_{i, j} = \max_{k = j + 1}^{j + \mathit{BS}_i}\{f_{i - w - 1, k} + (k - j) \times \mathit{BP}_i\}$。

不难发现，$3$ 和 $4$ 两个操作是可以被优化的。

$3$ 中的方程可以被转化为：

$$\begin{aligned} f_{i, j} &= \max_{k = j - \mathit{AS}_i}^{j - 1}\{f_{i - w - 1, k} - (j - k) \times \mathit{AP}_i\} \\ &= \max_{k = j - \mathit{AS}_i}^{j - 1}\{f_{i - w - 1, k} - j \times \mathit{AP}_i + k \times \mathit{AP}_i\} \\ &= \max_{k = j - \mathit{AS}_i}^{j - 1}\{f_{i - w - 1, k} + k \times \mathit{AP}_i\} - j \times \mathit{AP}_i \\ \end{aligned}$$

同理，$4$ 中的方程可以被转化为：

$$\begin{aligned} f_{i, j} &= \max_{k = j + 1}^{j + \mathit{BS}_i}\{f_{i - w - 1, k} + (k - j) \times \mathit{BP}_i\} \\ &= \max_{k = j + 1}^{j + \mathit{BS}_i}\{f_{i - w - 1, k} + k \times \mathit{BP}_i - j \times \mathit{BP}_i\} \\ &= \max_{k = j + 1}^{j + \mathit{BS}_i}\{f_{i - w - 1, k} + k \times \mathit{BP}_i\} - j \times \mathit{BP}_i \\ \end{aligned}$$

使用单调队列维护即可。

#代码

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

#include <iostream>
#include <cstring>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2005;

int n, m, w, f[N][N];

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(f, 0xcf, sizeof(f));

    cin >> n >> m >> w;

    for (int i = 1; i <= n; i++) {
        f[i][0] = 0;

        int ap, bp, as, bs;

        cin >> ap >> bp >> as >> bs;

        // [2]: 从 0 张开始买入
        for (int j = 0; j <= as; j++) {
            f[i][j] = -j * ap;
        }

        // [1]: 不操作
        for (int j = 0; j <= m; j++) {
            f[i][j] = std::max(f[i][j], f[i - 1][j]);
        }

        if (i - w - 1 > 0) {
            // [3]: 买入
            for (int j = 0; j <= m; j++) {
                for (int k = std::max(j - as, 0); k < j; k++) {
                    f[i][j] = std::max(f[i][j], f[i - w - 1][k] - (j - k) * ap);
                }
            }

            // [4]: 卖出
            for (int j = 0; j <= m; j++) {
                for (int k = j + 1; k <= std::min(j + bs, m); k++) {
                    f[i][j] = std::max(f[i][j], f[i - w - 1][k] + (k - j) * bp);
                }
            }
        }
    }

    cout << f[n][0] << endl;

    return 0;
}

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

#include <iostream>
#include <cstring>
#include <deque>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2005;

int n, m, w, f[N][N];

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(f, 0xcf, sizeof(f));

    cin >> n >> m >> w;

    for (int i = 1; i <= n; i++) {
        f[i][0] = 0;

        int ap, bp, as, bs;

        cin >> ap >> bp >> as >> bs;

        // [2]: 从 0 张开始买入
        for (int j = 0; j <= as; j++) {
            f[i][j] = -j * ap;
        }

        // [1]: 不操作
        for (int j = 0; j <= m; j++) {
            f[i][j] = std::max(f[i][j], f[i - 1][j]);
        }

        if (i - w - 1 > 0) {
            // [3]: 买入
            std::deque<int> q1;
            for (int j = 0; j <= m; j++) {
                while (!q1.empty() && q1.front() < j - as) q1.pop_front();
                while (!q1.empty() && f[i - w - 1][q1.back()] + q1.back() * ap <= f[i - w - 1][j] + j * ap) q1.pop_back();
                q1.push_back(j);
                f[i][j] = std::max(f[i][j], f[i - w - 1][q1.front()] - (j - q1.front()) * ap);
            }

            // [4]: 卖出
            std::deque<int> q2;
            for (int j = m; ~j; j--) {
                while (!q2.empty() && q2.front() > j + bs) q2.pop_front();
                while (!q2.empty() && f[i - w - 1][q2.back()] + q2.back() * bp <= f[i - w - 1][j] + j * bp) q2.pop_back();
                q2.push_back(j);
                f[i][j] = std::max(f[i][j], f[i - w - 1][q2.front()] + (q2.front() - j) * bp);
            }
        }
    }

    cout << f[n][0] << endl;

    return 0;
}