[CSP-J 2019] 纪念品

GitHub 跳转原题关系图返回列表

把相邻两天的价格差当作收益，按每天做一次完全背包，逐步更新手里的金币。

OJ: luogu

题目 ID: P5662

难度:普及+/提高

标签:动态规划完全背包背包

日期: 2026-06-19 17:24

前置题目

luogu U613136【力扣】买卖股票的最佳时机 II先理解相邻两天价格差为正才值得买卖的股票模型，再把单物品交易扩展为每天一次完全背包。

后置题目

luogu P2569[SCOI2010] 股票交易先掌握按相邻价格差建模交易收益，并把每天的可交易选择转成背包，再学习带持股数、交易冷却和单调队列优化的股票 DP。

题意

有 T 天、N 种纪念品，初始有 M 枚金币。

第 i 天，第 j 种纪念品的价格是 P[i][j]。每天可以无限次买卖任意纪念品，同一天里卖掉得到的金币可以立刻继续买别的纪念品。

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

static int T, N;
static vector<vector<int>> price;
static vector<vector<int>> memo_day;
static vector<vector<vector<int>>> memo_pick;

static int pick_profit(int day, int idx, int money) {
    if (idx == N) {
        return 0;
    }

    int &res = memo_pick[day][idx][money];
    if (res != -1) {
        return res;
    }

    // 不选当前纪念品，直接看后面的种类。
    res = pick_profit(day, idx + 1, money);

    int cost = price[day][idx];
    int gain = price[day + 1][idx] - price[day][idx];
    // 枚举当前纪念品买 1 件、2 件、... 的情况。
    for (int cnt = 1; cnt * cost <= money; ++cnt) {
        res = max(res, pick_profit(day, idx + 1, money - cnt * cost) + cnt * gain);
    }

    return res;
}

static int solve(int day, int money) {
    if (day == T - 1) {
        return money;
    }

    int &res = memo_day[day][money];
    if (res != -1) {
        return res;
    }

    // 当前这一天能赚到的最大额外金币。
    int gain = pick_profit(day, 0, money);
    res = solve(day + 1, money + gain);
    return res;
}

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

    int M;
    cin >> T >> N >> M;

    price.assign(T, vector<int>(N));
    for (int i = 0; i < T; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> price[i][j];
        }
    }

    memo_day.assign(T, vector<int>(10005, -1));
    memo_pick.assign(T, vector<vector<int>>(N + 1, vector<int>(10005, -1)));

    cout << solve(0, M) << '\n';
    return 0;
}

下面是另一种「01 序列」风格的暴力写法。它把每一个小选择拆成 $0/1$ 决策，递归生成完整购买序列后，叶子节点统一检查花费是否不超过当前钱数，并统计收益：

另一种暴力写法：01 序列

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// brute_01_style.cpp：01 序列风格暴力，把每天能买的每一件纪念品看成选/不选。
#include <bits/stdc++.h>
using namespace std;

struct Choice {
    int cost;
    int gain;
};

const int MAXT = 105;
const int MAXN = 105;

int T, N, start_money;
int price[MAXT][MAXN];
vector<Choice> choices;
vector<int> choose_buy; // choose_buy[i] = 0/1，表示第 i 件候选纪念品不买/买
int current_money;
int best_gain;

bool check() {
    int cost = 0;
    for (int i = 0; i < (int)choices.size(); i++) {
        if (choose_buy[i] == 1) cost += choices[i].cost;
    }
    return cost <= current_money;
}

int calc_gain() {
    int gain = 0;
    for (int i = 0; i < (int)choices.size(); i++) {
        if (choose_buy[i] == 1) gain += choices[i].gain;
    }
    return gain;
}

void dfs_choice(int dep) {
    if (dep == (int)choices.size()) {
        if (check()) {
            int value = calc_gain();
            if (best_gain < value) best_gain = value;
        }
        return;
    }

    // 第 dep 件候选纪念品的 01 选择：0 不买，1 买。
    for (int i = 0; i <= 1; i++) {
        choose_buy[dep] = i;
        dfs_choice(dep + 1);
    }
}

int best_gain_one_day(int day, int money) {
    choices.clear();

    for (int item = 1; item <= N; item++) {
        int cost = price[day][item];
        int gain = price[day + 1][item] - price[day][item];
        if (gain <= 0) {
            continue;
        }

        // 同一种纪念品可以买多件，这里把每一件展开成一个 01 选择。
        for (int cnt = 1; cnt * cost <= money; cnt++) {
            choices.push_back({cost, gain});
        }
    }

    choose_buy.assign(choices.size(), 0);
    current_money = money;
    best_gain = 0;
    dfs_choice(0);
    return best_gain;
}

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

    cin >> T >> N >> start_money;
    for (int day = 1; day <= T; day++) {
        for (int item = 1; item <= N; item++) {
            cin >> price[day][item];
        }
    }

    int money = start_money;
    for (int day = 1; day < T; day++) {
        money += best_gain_one_day(day, money);
    }

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

brute.cpp 直接枚举每天能买多少件、怎么组合，能正确反映题意，但只适合小数据。

这题最关键的观察是：我们不需要关心“纪念品一直持有了几天”，只需要关心“在某一天和下一天之间，哪些纪念品值得持有”。

也就是说，考虑相邻两天 i 和 i + 1：

如果某个纪念品今天买入、明天卖出，那么每件的收益就是 P[i+1][j] - P[i][j]
买入时消耗的是 P[i][j]
同一天可以买很多件，所以是完全背包

这张表说明一个日间转移的含义：

状态	含义
`money`	当前手里的金币
`dp[x]`	用不超过 `x` 枚金币，在这一段时间里能额外赚到的最大金币
`P[i][j]`	今天买入这一件的代价
`P[i+1][j] - P[i][j]`	持有到明天再卖出的净收益

于是每天都可以做一次完全背包：

以当天手里的金币 money 作为容量
对每个纪念品，重量是今天的价格，价值是明天比今天多赚的钱
跑完完全背包后，dp[money] 就是这一晚最多能多赚的金币
令 money += dp[money]，进入下一天

如果某个纪念品的净收益不是正数，就不选它。因为完全背包本来就允许“什么都不买”，所以这种情况直接跳过即可。

DP 公式

处理第 $i$ 天到第 $i+1$ 天时，当前金币为 $money$ 。设 $dp_x$ 表示用不超过 $x$ 枚金币在这一晚能额外赚到的最大金币。对第 $j$ 种纪念品：

weight=P_{i,j},\quad value=P_{i+1,j}-P_{i,j}

若 $value>0$ ，做完全背包转移：

dp_x=\max(dp_x,\ dp_{x-weight}+value)

这一晚结束后：

money\leftarrow money+dp_{money}

公式解释：一天到下一天之间，买入价是容量消耗，价格差是收益。每天用当前金币做一次完全背包，算出这一晚最多能赚多少，再把收益加入金币进入下一天。

样例 1 DP 表格

以样例 1 为例： $T = 6, N = 1, M = 100$ ，唯一纪念品每天的价格为 $[50, 20, 25, 20, 25, 50]$ 。

天 $i \to i+1$	买入价 $weight$	价格差 $value$	当前金币 $money$	完全背包结果 $dp_{money}$	更新后金币
1 → 2	50	$20 - 50 = -30$	100	0（ $value \leqslant 0$ ，跳过）	100
2 → 3	20	$25 - 20 = 5$	100	$\lfloor 100/20 \rfloor \times 5 = 25$	125
3 → 4	25	$20 - 25 = -5$	125	0（ $value \leqslant 0$ ，跳过）	125
4 → 5	20	$25 - 20 = 5$	125	$\lfloor 125/20 \rfloor \times 5 = 30$	155
5 → 6	25	$50 - 25 = 25$	155	$\lfloor 155/25 \rfloor \times 25 = 150$	305

最终金币为 $305$ ，与样例输出一致。关键操作是第 2 天低价买入、第 3 天卖出获利，第 4 天再低价买入、第 5 天卖出，最后第 5 天再买入、第 6 天高价卖出。

代码

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

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

    int T, N, money;
    cin >> T >> N >> money;

    vector<vector<int>> price(T, vector<int>(N));
    for (int i = 0; i < T; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> price[i][j];
        }
    }

    // 逐天处理相邻两天之间的收益，把金币滚动更新。
    for (int day = 0; day + 1 < T; ++day) {
        vector<int> dp(money + 1, 0);

        for (int item = 0; item < N; ++item) {
            int cost = price[day][item];
            int gain = price[day + 1][item] - price[day][item];
            if (gain <= 0 || cost > money) {
                continue;
            }

            // 完全背包：同一种纪念品可以买很多件。
            for (int cap = cost; cap <= money; ++cap) {
                dp[cap] = max(dp[cap], dp[cap - cost] + gain);
            }
        }

        money += dp[money];
    }

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

复杂度

时间复杂度： $O(T * N * M)$
空间复杂度： $O(M)$

这里 $M <= 10^3$ ， $T <= 100$ ， $N <= 100$ ，所以这个复杂度足够。

总结

这题表面上是“买纪念品”，本质上是“每天都做一次完全背包”。

真正要抓住的是两点：

物品重量是今天的买入价
物品价值是明天和今天的价格差

把每天的最优增益算出来，再把金币滚动更新，就能得到最终答案。

一图流解析

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

P5662 [CSP-J 2019] 纪念品

题目描述

小伟突然获得一种超能力，他知道未来 $T$ 天 $N$ 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。

每天，小伟可以进行以下两种交易无限次：

任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；
卖出持有的任意一个纪念品，以当日价格换回金币。

每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。

$T$ 天之后，小伟的超能力消失。因此他一定会在第 $T$ 天卖出所有纪念品换回金币。

小伟现在有 $M$ 枚金币，他想要在超能力消失后拥有尽可能多的金币。

输入格式

第一行包含三个正整数 $T, N, M$ ，相邻两数之间以一个空格分开，分别代表未来天数 $T$ ，纪念品数量 $N$ ，小伟现在拥有的金币数量 $M$ 。

接下来 $T$ 行，每行包含 $N$ 个正整数，相邻两数之间以一个空格分隔。第 $i$ 行的 $N$ 个正整数分别为 $P_{i,1},P_{i,2},\dots,P_{i,N}$ ，其中 $P_{i,j}$ 表示第 $i$ 天第 $j$ 种纪念品的价格。

输出格式

输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

说明/提示

样例 1 说明

最佳策略是：

第二天花光所有 $100$ 枚金币买入 $5$ 个纪念品 $1$ ；

第三天卖出 $5$ 个纪念品 $1$ ，获得金币 $125$ 枚；

第四天买入 $6$ 个纪念品 $1$ ，剩余 $5$ 枚金币；

第六天必须卖出所有纪念品换回 $300$ 枚金币，第四天剩余 $5$ 枚金币，共 $305$ 枚金币。

超能力消失后，小伟最多拥有 $305$ 枚金币。

样例 2 说明

最佳策略是：

第一天花光所有金币买入 $10$ 个纪念品 $1$ ；

第二天卖出全部纪念品 $1$ 得到 $150$ 枚金币并买入 $8$ 个纪念品 $2$ 和 $1$ 个纪念品 $3$ ，剩余 $1$ 枚金币；

第三天必须卖出所有纪念品换回 $216$ 枚金币，第二天剩余 $1$ 枚金币，共 $217$ 枚金币。

超能力消失后，小伟最多拥有 $217$ 枚金币。

数据规模与约定

对于 $10\%$ 的数据， $T = 1$ 。

对于 $30\%$ 的数据， $T \leq 4, N \leq 4, M \leq 100$ ，所有价格 $10 \leq P_{i,j} \leq 100$ 。

另有 $15\%$ 的数据， $T \leq 100, N = 1$ 。

另有 $15\%$ 的数据， $T = 2, N \leq 100$ 。

对于 $100\%$ 的数据， $T \leq 100, N \leq 100, M \leq 10^3$ ，所有价格 $1 \leq P_{i,j} \leq 10^4$ ，数据保证任意时刻，小伟手上的金币数不可能超过 $10^4$ 。

[CSP-J 2019] 纪念品

目录

题意

思路

DP 公式

样例 1 DP 表格

代码

复杂度

总结

一图流解析