[SCOI2010] 股票交易

题意

有 T 天的已知股票价格。

第 i 天：

买入价是 AP_i
卖出价是 BP_i
一次最多买 AS_i 股
一次最多卖 BS_i 股

还有限制：

如果某天进行了买入或卖出，那么接下来连续 W 天都不能再交易
任意时刻持股数不能超过 MaxP

开始时没有股票、资金看作无限，要求最大化 T 天结束后的收益。

思路

先看一个适合小数据验证的暴力：

cpp

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#include <bits/stdc++.h>
using namespace std;

const long long NEG_INF = -(1LL << 60);

int T, MaxP, W;
int ap[25], bp[25], as[25], bs[25];
// memo[day][hold][wait]：
// 从第 day 天开始，当前持有 hold 股，还要再等 wait 天才能继续交易时，
// 从现在到最后一天能够得到的最大额外收益。
long long memo[25][25][25];
int vis[25][25][25];

long long dfs(int day, int hold, int wait) {
    if (day > T) {
        return 0;
    }
    if (vis[day][hold][wait]) {
        return memo[day][hold][wait];
    }
    vis[day][hold][wait] = 1;

    int next_wait = wait;
    if (next_wait > 0) {
        next_wait--;
    }

    // 今天不交易。
    long long best = dfs(day + 1, hold, next_wait);

    if (wait == 0) {
        // 今天买一些股票。
        int max_buy = min(as[day], MaxP - hold);
        for (int x = 1; x <= max_buy; x++) {
            best = max(best, dfs(day + 1, hold + x, W) - 1LL * x * ap[day]);
        }

        // 今天卖一些股票。
        int max_sell = min(bs[day], hold);
        for (int x = 1; x <= max_sell; x++) {
            best = max(best, dfs(day + 1, hold - x, W) + 1LL * x * bp[day]);
        }
    }

    memo[day][hold][wait] = best;
    return best;
}

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

    // brute.cpp：小数据记忆化搜索。
    // 直接枚举每天买多少、卖多少，或者什么都不做，用来帮助理解题意并辅助对拍。
    cin >> T >> MaxP >> W;
    for (int i = 1; i <= T; i++) {
        cin >> ap[i] >> bp[i] >> as[i] >> bs[i];
    }

    memset(vis, 0, sizeof(vis));
    cout << dfs(1, 0, 0) << '\n';
    return 0;
}

暴力搜索把状态写成 (day, hold, wait)：

day 表示当前处理到第几天
hold 表示手里持有多少股
wait 表示还要再等几天才能继续交易

每一天直接枚举三种行为：

不交易
买 1..AS_i 股
卖 1..BS_i 股

这样虽然直观，但显然只能跑很小的数据。

正解用动态规划。

设 dp[i][j] 表示第 i 天结束时，手里持有 j 股股票的最大净收益。

今天如果什么都不做，那么：

dp[i][j] = dp[i-1][j]

如果今天要交易，因为两次交易之间至少间隔 W 天，上一次交易只能发生在 i-W-1 天或更早。

记：

pre = max(0, i-W-1)

由于中间这些天都可以视为“什么都不做”，更早的状态已经被传到了 dp[pre][*] 里，所以今天的买卖只需要从 dp[pre][*] 转移。

如果今天买入，原来持有 k 股，今天买了 j-k 股，那么要满足：

k <= j
j-k <= AS_i

转移式是：

dp[i][j] = max(dp[pre][k] - (j-k) * AP_i)

整理一下：

dp[i][j] = -j * AP_i + max(dp[pre][k] + k * AP_i)

其中 k 的范围是 [j-AS_i, j]。

对固定的一天来说，j 从小到大枚举时，这个 k 的可选范围就是一个不断右移的滑动窗口，所以可以用单调队列维护窗口内

dp[pre][k] + k * AP_i

的最大值。

卖出同理。

如果原来持有 k 股，今天卖掉 k-j 股，那么：

k >= j
k-j <= BS_i

转移式是：

dp[i][j] = max(dp[pre][k] + (k-j) * BP_i)

整理后变成：

dp[i][j] = -j * BP_i + max(dp[pre][k] + k * BP_i)

其中 k 的范围是 [j, j+BS_i]。

这也是一个滑动窗口最大值问题，只不过这里从大到小枚举 j 更顺手。

于是每一天只需要做三件事：

继承昨天“不交易”的状态
用单调队列做一遍买入转移
用单调队列做一遍卖出转移

总复杂度就从朴素的 $O(T * MaxP^2)$ 降到了 $O(T * MaxP)$ 。

DP 转移方程

核心状态：

dp[i][j] 为第 i 天结束持有 j 股最大收益

核心转移：

买: -j*AP_i+max(dp[pre][k]+k*AP_i)；卖: -j*BP_i+max(dp[pre][k]+k*BP_i)

答案收束：

max_j dp[T][j]

代码

cpp

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106#include <bits/stdc++.h>
using namespace std;

const int MAXT = 2005;
const int MAXP = 2005;
const long long NEG_INF = -(1LL << 60);

int T, MaxP, W;
int ap[MAXT], bp[MAXT], as[MAXT], bs[MAXT];
// dp[day][hold]：到第 day 天结束时，手里持有 hold 股股票的最大净收益。
long long dp[MAXT][MAXP];
// 单调队列里存的是候选持股数下标。
int q[MAXP];

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

    cin >> T >> MaxP >> W;
    for (int i = 1; i <= T; i++) {
        cin >> ap[i] >> bp[i] >> as[i] >> bs[i];
    }

    for (int i = 0; i <= T; i++) {
        for (int j = 0; j <= MaxP; j++) {
            dp[i][j] = NEG_INF;
        }
    }
    dp[0][0] = 0;

    for (int day = 1; day <= T; day++) {
        // 今天什么都不做，直接继承昨天的状态。
        for (int hold = 0; hold <= MaxP; hold++) {
            dp[day][hold] = dp[day - 1][hold];
        }

        // 如果今天发生交易，那么上一次交易最晚只能在 pre 这一天或更早。
        // 更早的状态已经通过“什么都不做”的转移传到了 dp[pre][*] 里。
        int pre = day - W - 1;
        if (pre < 0) {
            pre = 0;
        }

        // 买入转移：
        // dp[day][hold] = max(dp[pre][k] - (hold-k)*ap[day])
        // = -hold*ap[day] + max(dp[pre][k] + k*ap[day])
        int head = 0, tail = -1;
        for (int hold = 0; hold <= MaxP; hold++) {
            while (head <= tail && q[head] < hold - as[day]) {
                head++;
            }

            long long cur_value = dp[pre][hold] + 1LL * hold * ap[day];
            while (head <= tail) {
                int last = q[tail];
                long long last_value = dp[pre][last] + 1LL * last * ap[day];
                if (last_value <= cur_value) {
                    tail--;
                } else {
                    break;
                }
            }
            q[++tail] = hold;

            int best = q[head];
            dp[day][hold] = max(dp[day][hold],
                                dp[pre][best] - 1LL * (hold - best) * ap[day]);
        }

        // 卖出转移：
        // dp[day][hold] = max(dp[pre][k] + (k-hold)*bp[day])
        // = -hold*bp[day] + max(dp[pre][k] + k*bp[day])
        head = 0;
        tail = -1;
        for (int hold = MaxP; hold >= 0; hold--) {
            while (head <= tail && q[head] > hold + bs[day]) {
                head++;
            }

            long long cur_value = dp[pre][hold] + 1LL * hold * bp[day];
            while (head <= tail) {
                int last = q[tail];
                long long last_value = dp[pre][last] + 1LL * last * bp[day];
                if (last_value <= cur_value) {
                    tail--;
                } else {
                    break;
                }
            }
            q[++tail] = hold;

            int best = q[head];
            dp[day][hold] = max(dp[day][hold],
                                dp[pre][best] + 1LL * (best - hold) * bp[day]);
        }
    }

    // 枚举最后一天结束时的持股数，取最大净收益。
    long long ans = 0;
    for (int hold = 0; hold <= MaxP; hold++) {
        ans = max(ans, dp[T][hold]);
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度 $O(T * MaxP)$ ，空间复杂度 $O(T * MaxP)$ 。

总结

这题的关键不是“股票”背景，而是把状态转移改写成区间最值。

一旦发现对固定的一天来说，合法前驱 k 会随着持股数 j 的变化形成滑动窗口，就可以自然地想到用单调队列优化 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。