2019真题 | 纪念品 luogu-P5662 – 【# 日积月累】

2019真题 | 纪念品 luogu-P5662

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

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

输出 #1

输入输出样例 #2

输入 #2

输出 #2

说明/提示

【样例解释 #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$ 天开始，令当前的资金为 $M$ 。
循环每一天 $i$ $i$ （从 $1$ $1$ 到 $T-1$ $T - 1$ ）：
- 初始化 $dp$ 数组为 $0$ 。
- 遍历每一种物品 $j$ （从 $1$ 到 $N$ ），如果其下一天的价格大于今天，则用完全背包的方式正向更新 $dp[w]$ 。
- 这一天决策完后，更新资金 $M \gets M + dp[M]$ 。
循环结束后，最终的 $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 秒即可跑完，完全不会超时。

示例代码

#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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年6月16日

2021真题 | 网络连接 luogu-P7911 2022真题 | 乘方 luogu-P8813