「一本通 5.5 练习 4」股票交易

形式化题目

已知 $T$ 天行情：第 $i$ 天买入价 $AP_i$ 、卖出价 $BP_i$ （保证 $AP_i \geqslant BP_i$ ），一次买入至多 $AS_i$ 股、一次卖出至多 $BS_i$ 股。规则：

某一天的买入或卖出均算一次交易，两次交易之间至少间隔 $W$ 天（第 $i$ 天交易后， $i+1 \sim i+W$ 天不能交易）；
任何时刻持仓不超过 $MaxP$ ；
初始资金无限、持股 0——资金无限意味着买入总能成交，因此求的是净增金额的最大值（记账以 0 为初始现金，允许现金为负）。

求 $T$ 天后的最大现金。

每天只允许至多一个动作（不交易 / 买一批 / 卖一批）是不失一般性的：同日往返必亏（ $AP_i \geqslant BP_i$ ），先卖后买与一次净操作等价且更差。第 $i$ 天若要交易，上一次交易日必须 $\leqslant i - W - 1$ ，于是"交易的前驱状态"固定为第 $\max(i - W - 1, 0)$ 天结束时的状态——这个观察是全题的支点。

样例 $T = 5,\ MaxP = 2,\ W = 0$ （相邻天可交易）的一组最优安排如下，最终现金 3：

天	1	2	3	4	5
动作	买 1 股 @ $2$	买 1 股 @ $2$	不交易	卖 1 股 @ $3$	卖 1 股 @ $4$
持股	1	2	2	1	0
现金	$-2$	$-4$	$-4$	$-1$	$3$

第 3 天不交易使第 4、5 天连续交易仍然合法（ $W = 0$ ）；两天买入共花 4，两卖收 7，净赚 $7 - 4 = 3$ ，与输出一致。

正解

思路

朴素 DP 与瓶颈。 设 $f[i][j]$ 为第 $i$ 天结束时持有 $j$ 股的最大现金， $f[0][0] = 0$ 、其余 $-\infty$ 。记前驱 $p = \max(i - W - 1, 0)$ ，转移三选一：

f[i][j] = \max\Big(\,f[i-1][j],\ \max_{j' \in [j - AS_i,\, j - 1]}\!\big(f[p][j'] - AP_i (j - j')\big),\ \max_{j' \in [j + 1,\, j + BS_i]}\!\big(f[p][j'] + BP_i (j' - j)\big)\Big).

第一项是当天不交易；后两项分别是从前驱状态买入、卖出。间隔 $W$ 已由前驱 $p$ 编码，持仓上限由 $j \leqslant MaxP$ 与窗口长度编码。答案是 $\max_j f[T][j]$ ——末尾持股不算钱，但最后一天未必卖得出去，所以要对所有持股数取最大。

若对每个 $(i, j)$ 直接扫两个窗口，单次判定 $AS_i + BS_i$ 长度，总计 $O(T \cdot MaxP \cdot (AS + BS))$ ，最坏 $O(T \cdot MaxP^2) = 8 \times 10^9$ ，跑不动。瓶颈就在这两个随 $j$ 平移的固定窗口最值上。

拆项：窗口里被最大的量与 $j$ 无关。 把代价按 $j'$ 拆开：

f[p][j'] - AP_i (j - j') = \big(f[p][j'] + AP_i \, j'\big) - AP_i \, j, \qquad f[p][j'] + BP_i (j' - j) = \big(f[p][j'] + BP_i \, j'\big) - BP_i \, j.

对固定的第 $i$ 天，减去的 $AP_i \, j$ / $BP_i \, j$ 不参与窗口比较，于是问题变成：维护 $g(j') = f[p][j'] + \text{price} \cdot j'$ 在窗口内的最大值。 $j$ 每加 1，买入窗口 $[j - AS_i, j - 1]$ 整体右移一格（右端进一个、左端出一个）；卖出时 $j$ 每减 1，窗口 $[j + 1, j + BS_i]$ 整体左移一格。单调队列按 $g(j')$ 递减（买入）/ 递增（卖出）维护，每个下标至多入队、出队各一次，摊还 $O(1)$ ，单天 $O(MaxP)$ 。

样例的 DP 全程（ $W = 0$ 时前驱就是 $f[i-1]$ ，窗口长度 $AS_i = BS_i = 1$ ）：

第 $i$ 天	$f[i][0]$	$f[i][1]$	$f[i][2]$	关键转移
0（初始）	0	$-\infty$	$-\infty$	$f[0][0]=0$ ，尚不能持股
1	0	$-2$	$-\infty$	买： $f[0][0] - 2 \times 1 = -2$
2	0	$-2$	$-4$	买： $f[1][1] - 2 \times 1 = -4$
3	0	$-2$	$-4$	买 @ $3$ 、卖 @ $2$ 都不优于继承，不变
4	$1$	$-1$	$-4$	卖： $f[3][1] + 3 \times 1 = 1$ ； $f[3][2] + 3 \times 1 = -1$
5	$3$	$0$	$-4$	卖： $f[4][1] + 4 \times 1 = 3$

观察表中两点： $i = 1$ 时 $AS_1 = 1$ 所以 $f[1][2] = -\infty$ （一天只能买 1 股，买不齐 2 股）；答案 3 来自第 5 天卖出窗口命中 $f[4][1] = -1$ ，正是"第 4、5 天连续两天各卖 1 股"那条路线。最终 $\max_j f[5][j] = 3$ 。

实现上 $f[i]$ 只依赖 $f[i-1]$ 和距今 $W+1$ 天的 $f[p]$ ，历史快照用长度 $W + 2$ 的环形数组保存即可，不必留整张 $T \times MaxP$ 表。

代码

与正文符号的对应： $f[i][j]$ 是滚动数组 dp，前驱 $p$ 的快照是 base（环形历史 hist）， $g(j')$ 即 base[idx] + price * idx；transfer_buy / transfer_sell 分别是买入、卖出两个单调队列转移，NEG = -10**18 充当 $-\infty$ （真实钱数下界约 $-2000^3 = -8 \times 10^9$ ，不会混淆）；solve 读入后逐天滚动，最后 max(dp) 出答案。

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 21:22
# update_at: 2026-09-30 21:22

import sys
from array import array
from collections import deque

NEG = -10**18  # 不可达哨兵：真实钱数下界约 -2000×2000×2000 = -8e9，远离此值


def transfer_buy(base: array, price: int, limit: int, max_p: int, dp: array) -> None:
    """买入转移：对每个 j，从窗口 j' ∈ [j-limit, j-1] 里取 base[j']-price*(j-j') 的最大值写进 dp。"""
    q: deque[int] = deque()  # 单调队列存下标，按 base[j']+price*j' 单调递减，队头即窗口最大
    for j in range(1, max_p + 1):
        nj = j - 1  # 窗口右端新进来的持股数
        v = base[nj] + price * nj
        while q and base[q[-1]] + price * q[-1] <= v:
            q.pop()
        q.append(nj)
        out = j - limit - 1  # 刚滑出窗口左端的持股数；它是队里最小下标，若在则必在队头
        if out >= 0 and q[0] == out:
            q.popleft()
        best = q[0]
        cand = base[best] + price * (best - j)  # = base[best] - price*(j-best)
        if cand > dp[j]:
            dp[j] = cand


def transfer_sell(base: array, price: int, limit: int, max_p: int, dp: array) -> None:
    """卖出转移：对每个 j，从窗口 j' ∈ [j+1, j+limit] 里取 base[j']+price*(j'-j) 的最大值写进 dp。"""
    q: deque[int] = deque()
    for j in range(max_p - 1, -1, -1):  # 窗口整体左移，从大到小枚举 j
        while q and q[-1] > j + limit:  # 右端（下标最大者）先滑出窗口
            q.pop()
        nj = j + 1  # 窗口左端新进来的持股数
        v = base[nj] + price * nj
        while q and base[q[0]] + price * q[0] <= v:  # 队头被更晚过期的更大值压制，弹出
            q.popleft()
        q.appendleft(nj)
        best = q[-1]  # 队里按值单调递增，队尾即窗口最大
        cand = base[best] + price * (best - j)  # = base[best] + price*(best-j)
        if cand > dp[j]:
            dp[j] = cand


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    days, max_p, W = next(data), next(data), next(data)
    AP = [0] * days  # 每天买入价
    BP = [0] * days  # 每天卖出价
    AS = [0] * days  # 每天一次买入的股数上限
    BS = [0] * days  # 每天一次卖出的股数上限
    for i in range(days):
        AP[i], BP[i], AS[i], BS[i] = next(data), next(data), next(data), next(data)

    # 环形历史快照：第 d 天结束时的持股状态；第 i 天交易只回看 d = i-W-1 的快照
    ring = W + 2
    day0 = array("q", [0] + [NEG] * max_p)  # 开盘前：0 股 0 钱，唯一可达状态
    hist: list[array | None] = [None] * ring
    hist[0] = day0
    dp = day0  # 截至昨天的状态；每天先原样继承（当天不交易）

    for day in range(1, days + 1):
        prev_day = day - W - 1  # 两次交易至少隔 W 天：上次交易最晚在 prev_day
        base = day0 if prev_day < 0 else hist[prev_day % ring]
        dp = array("q", dp)  # 继承「昨天也不交易」
        if AS[day - 1]:  # 买入：多持有 1..AS 股，每股花 AP
            transfer_buy(base, AP[day - 1], AS[day - 1], max_p, dp)
        if BS[day - 1]:  # 卖出：少持有 1..BS 股，每股收 BP
            transfer_sell(base, BP[day - 1], BS[day - 1], max_p, dp)
        hist[day % ring] = dp

    print(max(dp))  # 结束时持股任意（不交易就是 0 股），取钱数最大


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:15
 * update_at: 2026-10-05 12:15
 *
 * 股票交易（SCOI 2010 / 一本通 5.5 练习 4）
 * DP：f[i][j] = 第 i 天结束时持有 j 股的最大现金。
 * 第 i 天交易的前驱固定为第 p = max(i-W-1, 0) 天结束时的状态（间隔 W 天）。
 * 买入/卖出转移各是一个随 j 平移的固定长度窗口最值，拆项后用单调队列摊还 O(1)，
 * 总复杂度 O(T * MaxP)。
 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 2005;
const ll NEG = -1000000000000000000LL; // 不可达哨兵：真实钱数下界约 -8e9，远离此值

int T, MaxP, W;
ll AP[MAXN], BP[MAXN]; // 第 i 天的买入价 / 卖出价
ll AS[MAXN], BS[MAXN]; // 第 i 天一次买入 / 卖出的股数上限
ll f[MAXN][MAXN];      // f[i][j]：第 i 天结束时持有 j 股的最大现金
int que[MAXN];         // 单调队列，存持股数下标
int qh, qt;            // 队头 / 队尾（半开区间 [qh, qt)）

// 买入转移：对每个 j，从窗口 j' ∈ [j-AS, j-1] 里取 f[p][j'] - AP*(j-j') 的最大值写进 f[i][j]
// 窗口里被比较的量 g(j') = f[p][j'] + AP*j' 与 j 无关，j 增大时窗口整体右移一格
void transfer_buy(int i, int p) {
    ll price = AP[i];
    ll limit = AS[i];
    qh = 0, qt = 0;
    for (int j = 1; j <= MaxP; j++) {
        int nj = j - 1; // 窗口右端新进来的持股数
        ll v = f[p][nj] + price * nj;
        while (qt > qh && f[p][que[qt - 1]] + price * que[qt - 1] <= v)
            qt--; // 值不大于新值的下标从队尾弹出，队列按 g 递减，队头即窗口最大
        que[qt++] = nj;
        int out = j - (int)limit - 1; // 刚滑出窗口左端的持股数；若还在队里必在队头
        if (out >= 0 && que[qh] == out)
            qh++;
        int best = que[qh];
        ll cand = f[p][best] + price * (best - j); // = f[p][best] - price*(j-best)
        if (cand > f[i][j])
            f[i][j] = cand;
    }
}

// 卖出转移：对每个 j，从窗口 j' ∈ [j+1, j+BS] 里取 f[p][j'] + BP*(j'-j) 的最大值写进 f[i][j]
// j 从大到小枚举，窗口整体左移；队列下标递减、g 值递减，队头即窗口最大
void transfer_sell(int i, int p) {
    ll price = BP[i];
    ll limit = BS[i];
    qh = 0, qt = 0;
    for (int j = MaxP - 1; j >= 0; j--) {
        while (qt > qh && que[qh] > j + limit)
            qh++; // 队头是队里最大下标，先滑出窗口右端
        int nj = j + 1; // 窗口左端新进来的持股数
        ll v = f[p][nj] + price * nj;
        while (qt > qh && f[p][que[qt - 1]] + price * que[qt - 1] <= v)
            qt--; // 队尾值不大于新值则弹出（它下标更大、更早过期，被完全压制）
        que[qt++] = nj;
        int best = que[qh];
        ll cand = f[p][best] + price * (best - j); // = f[p][best] + price*(best-j)
        if (cand > f[i][j])
            f[i][j] = cand;
    }
}

int main() {
    scanf("%d %d %d", &T, &MaxP, &W);
    for (int i = 1; i <= T; i++)
        scanf("%lld %lld %lld %lld", &AP[i], &BP[i], &AS[i], &BS[i]);

    // 第 0 天开盘前：0 股 0 钱，其余状态不可达
    for (int j = 1; j <= MaxP; j++)
        f[0][j] = NEG;

    for (int i = 1; i <= T; i++) {
        int p = i - W - 1; // 上次交易最晚发生在第 p 天
        if (p < 0)
            p = 0;
        for (int j = 0; j <= MaxP; j++)
            f[i][j] = f[i - 1][j]; // 当天不交易：原样继承昨天
        if (AS[i] > 0)
            transfer_buy(i, p);
        if (BS[i] > 0)
            transfer_sell(i, p);
    }

    // 结束时持股任意（不交易即 0 股），对...
    ll ans = f[T][0];
    for (int j = 1; j <= MaxP; j++)
        if (f[T][j] > ans)
            ans = f[T][j];
    printf("%lld\n", ans);
    return 0;
}

复杂度

时间复杂度： $O(T \cdot MaxP)$ ——单调队列里每个持股数至多入队、出队各一次，每天买卖各扫一遍 $0 \sim MaxP$ ；与标准 C++ 解法（单调队列优化 DP）同阶。 $T = MaxP = 2000$ 时约 $4 \times 10^6$ 次基本操作。
空间复杂度： $O((W + 2) \cdot MaxP)$ ——环形保存 $W + 2$ 天快照（array('q') 每项 8 字节），最坏约 32 MB；朴素的 $O(T \cdot MaxP)$ 整表约 64 MB，环形已把它压掉。

总结

本题的关键是把间隔规则翻译成前驱下标：第 $i$ 天交易只能接在第 $\max(i - W - 1, 0)$ 天的状态后面，DP 因此只需"天 $\times$ 持股数"两维、每天两个窗口转移。朴素扫描的 $O(T \cdot MaxP^2)$ 瓶颈在于窗口最值，而把代价按 $j'$ 拆项后，窗口内被最大的量与 $j$ 无关，买卖窗口又分别随 $j$ 单向平移——单调队列摊还 $O(1)$ 把总复杂度降到 $O(T \cdot MaxP)$ 。易错点有三：前驱 $p \leqslant 0$ 时要退回初始状态（否则会漏掉"当天是第一次交易"）；卖出窗口的 $j$ 要从大到小枚举才能保持平移；末尾要对所有持股数取最大而不是只取 $j = 0$ 。实测真实数据 10/10 全部一致，单点 0.019–1.59 s、峰值 ≤ 36 MB，相对 1000 ms / 128 MB 的限制，Python 侧时间偏紧（允许 TLE）但内存宽裕。

「一本通 5.5 练习 4」股票交易

目录

形式化题目

正解

思路

代码

复杂度

总结