文章

【CSP】CSP-J 2019真题 | 纪念品 luogu-P5662 （适合GESP六级及以上考生练习）

发表于
作者 OneCoder
次浏览 15 分钟阅读

CSP-J 2019真题-纪念品，完全背包动态规划考点，重点考察如何将看似复杂的“跨天交易与长期持有”问题，优雅地拆解为每日独立的“当日买入、明日卖出”的完全背包问题。适合GESP六级及以上考生练习，难度⭐⭐⭐☆，洛谷难度等级普及+/提高。

P5662 [CSP-J 2019] 纪念品

题目要求

题目描述

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

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

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

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

$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
1
2
3
4
5
6
7

6 1 100
50
20
25
20
25
50
输出 #1
1

305

输入输出样例 #2

输入 #2
1
2
3
4

3 3 100
10 20 15
15 17 13
15 25 16
输出 #2
1

217

说明/提示

【样例解释 #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 \le 4, N \le 4, M \le 100$，所有价格 $10 \le P_{i,j} \le 100$。

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

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

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

题目分析

本题是一道非常经典的动态规划（DP）题目，表面上看似乎涉及复杂的“长期持有跨天卖出”决策，但通过仔细分析其交易机制，我们可以将其化繁为简。

1. 核心转化：为什么可以把“跨天持有”拆解为“每日独立交易”？

题目中提到：

  • “每天卖出纪念品换回的金币可以立即用于购买纪念品。”
  • “当日购买的纪念品也可以当日卖出。”
  • 且交易次数无限。

这意味着，如果我们持有一个纪念品跨越了多天（例如在第 $1$ 天买入，一直持有到第 $3$ 天卖出），它的利润是 $P_{3, j} - P_{1, j}$。 这完全等价于：

  • 在第 $1$ 天买入，在第 $2$ 天卖出（利润 $P_{2, j} - P_{1, j}$）。
  • 在第 $2$ 天立即以相同价格再买入，在第 $3$ 天卖出（利润 $P_{3, j} - P_{2, j}$）。

两天的累计收益为： \((P_{2, j} - P_{1, j}) + (P_{3, j} - P_{2, j}) = P_{3, j} - P_{1, j}\)

由于没有交易手续费，且交易次数无限，任何跨越数天的“长期持有”，都可以等价地拆解为每天“买入-次日卖出”的短线交易组合。

因此，我们不需要去记录当前手头持有了哪些纪念品、持有了多少天。我们只需要在每一天做出决策：利用手头的金币，买入哪些纪念品，并在下一天全部卖出，从而让下一天开始时的资金最大化。

2. 模型抽象：完全背包问题

如果我们只考虑从第 $i$ 天到第 $i+1$ 天：

  • 我们拥有初始资金 $M$（作为背包的总容量）。
  • 有 $N$ 种纪念品（作为物品）。
  • 每一个纪念品 $j$ 的购买成本是 $P_{i, j}$（作为物品的“重量”）。
  • 在第 $i+1$ 天卖出它能获得的收益为 $P_{i+1, j}$，扣除成本后，纯利润为 $P_{i+1, j} - P_{i, j}$（作为物品的“价值”）。
  • 每种纪念品可以购买无限次（完全背包）。

我们的目标是：求出在当前资金 $M$ 的限制下，选择购买哪些纪念品，能使第 $i+1$ 天获得的纯利润最大。 这就完全转换成了一个标准的完全背包问题：

  • 状态定义：$dp[w]$ 表示使用不超过 $w$ 枚金币在第 $i$ 天进行买入，并在第 $i+1$ 天卖出所能获得的最大利润。

  • 状态转移方程： \(dp[w] = \max(dp[w], dp[w - P_{i, j}] + P_{i+1, j} - P_{i, j})\)

    方程逻辑解析： 在第 $i$ 天面对第 $j$ 种纪念品，当手头资金容量为 $w$ 时，我们有两种选择：

    1. 不购买第 $j$ 种纪念品（或不再多买）：此时的最大利润保持不变，即当前的 dp[w]。
    2. 购买至少一个第 $j$ 种纪念品：既然决定购买，我们就需要支付其今日价格 $P_{i, j}$ 作为成本，此时剩余可用资金容量缩减为 $w - P_{i, j}$。而购买这一件纪念品能在明天卖出并为我们带来 $P_{i+1, j} - P_{i, j}$ 的纯利润。因此，该决策下的最大利润为 dp[w - P_{i, j}] + P_{i+1, j} - P_{i, j}。

    在这两项选择中取最大值（$\max$）即为当前资金容量 $w$ 下的最优决策。

    [!NOTE] 为什么是 dp[w - P_{i, j}] 而非前一个物品的状态？
    因为本题中每种纪念品可以购买无限次，这符合完全背包的模型。我们使用当前行中已经更新过的 dp[w - P_{i, j}] 状态进行转移，正向更新的过程天然允许了对同一种商品进行多次购买累加。如果使用的是上一轮迭代的状态，则会退化为每种物品最多只能买一件的 01 背包。

    其中，只有当 $P_{i+1, j} > P_{i, j}$（即利润大于 $0$）时，我们才有必要考虑买入该纪念品。

  • 资金更新：第 $i+1$ 天开始时，小伟手上的金币总数更新为 $M_{new} = M_{old} + dp[M_{old}]$。

3. 算法流程与复杂度

对于 $T$ 天，我们只需要进行 $T-1$ 轮完全背包决策：

  1. 从第 $1$ 天开始，令当前的资金为 $M$。
  2. 循环每一天 $i$（从 $1$ 到 $T-1$）：
    • 初始化 $dp$ 数组为 $0$。
    • 遍历每一种物品 $j$（从 $1$ 到 $N$），如果其下一天的价格大于今天，则用完全背包的方式正向更新 $dp[w]$。
    • 这一天决策完后，更新资金 $M \gets M + dp[M]$。
  3. 循环结束后，最终的 $M$ 即为所求。

数据范围与时间复杂度：

  • $T \le 100, N \le 100$。
  • 题目非常关键的提示：“数据保证任意时刻，小伟手上的金币数不可能超过 $10^4$。”
  • 因此，完全背包的容量上限 $M \le 10000$。
  • 每一轮完全背包的时间复杂度为 $O(N \cdot M)$。
  • 总时间复杂度为 $O(T \cdot N \cdot M)$。在最坏情况下，运算次数约为 $100 \times 100 \times 10000 = 10^8$ 次，在 C++ 中只需不到 0.05 秒即可跑完，完全不会超时。

示例代码

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

// 根据题目数据范围，任意时刻金币数不超过 10000，加上预留空间设定为 10005
const int MAXN = 105;
const int MAXT = 105;
const int MAXM = 10005;

int P[MAXT][MAXN]; // 记录第 i 天第 j 种纪念品的价格
int dp[MAXM];      // dp[w] 表示使用 w 金币能获得的最大利润

int main() {
    // 优化输入输出流性能
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T, N, M;
    std::cin >> T >> N >> M;

    // 读入 T 天 N 种纪念品的价格
    for (int i = 1; i <= T; i++) {
        for (int j = 1; j <= N; j++) {
            std::cin >> P[i][j];
        }
    }

    // T 天之间，共需进行 T-1 轮跨天的买卖决策
    for (int i = 1; i < T; i++) {
        // 每轮决策前将 dp 数组清零
        std::memset(dp, 0, sizeof(dp));

        for (int j = 1; j <= N; j++) {
            int cost = P[i][j];                // 今日买入价格（完全背包中的重量）
            int profit = P[i + 1][j] - P[i][j]; // 明日卖出所获得的纯利润（完全背包中的价值）

            // 只有明日价格高于今日价格（即能赚到钱）时，才考虑交易
            if (profit <= 0) continue;

            // 完全背包：正向遍历资金容量
            for (int w = cost; w <= M; w++) {
                dp[w] = std::max(dp[w], dp[w - cost] + profit);
            }
        }
        // 这一天的买卖完成后，获得的最大利润 dp[M] 累加进手头的金币 M 中，作为下一天的本金
        M += dp[M];
    }

    // 输出最终第 T 天结束卖出所有纪念品后，能拥有的最大金币数量
    std::cout << M << "\n";

    return 0;
}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

"luogu-"系列题目可在洛谷题库进行在线评测。

"bcqm-"系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
CSP, J
CSP C++ 动态规划 背包DP
本文由作者按照 CC BY-NC-SA 4.0 进行授权