这是一份符合 CSP-J/NOIP 标准的 AC 代码。

解题核心思路

1. 化繁为简：题目允许“当日买入当日卖出”，这意味着“在第 $i$ 天买入，持有到第 $k$ 天卖出”等价于“第 $i$ 天买第 $i+1$ 天卖，第 $i+1$ 天再买第 $i+2$ 天卖……”。因此，我们可以把 $T$ 天的交易拆解为 $T-1$ 轮独立的“今天买、明天卖”的交易。
2. 完全背包模型：对于每一轮（从第 $i$ 天到第 $i+1$ 天），我们的目标是利用手中的本金（背包容量），购买若干个纪念品（物品），使得明天能卖出的总价（价值）最大。因为每种纪念品可以买无限个，所以这是一个标准的完全背包问题。
   • 背包容量：当前拥有的金币数。
   • 物品花费：第 $i$ 天的价格。
   • 物品价值：第 $i+1$ 天的价格。
3. 状态转移：dp[j] 表示用 $j$ 元本金在明天能换回的最大金额。 dp[j] = max(dp[j], dp[j - 今日价格] + 明日价格)

标准 C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring> // 用于 memset

using namespace std;

// 根据题目数据范围：
// "数据保证任意时刻，小伟手上的金币数不可能超过 10^4"
// 所以 DP 数组开到 10005 足够了
const int MAX_MONEY = 10005; 
const int MAX_DAYS = 105;
const int MAX_ITEMS = 105;

int prices[MAX_DAYS][MAX_ITEMS]; // 存储每天每种商品的价格
int dp[MAX_MONEY];               // DP 数组

int main() {
    // 1. 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T, N, M;
    if (!(cin >> T >> N >> M)) return 0;

    // 2. 读入价格表
    for (int i = 1; i <= T; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> prices[i][j];
        }
    }

    // ans 表示当前手中的金币数，初始为 M
    int ans = M;

    // 3. 贪心 + 动态规划
    // 将整个过程拆分为 T-1 轮交易：
    // 第 1 天买 -> 第 2 天卖
    // 第 2 天买 -> 第 3 天卖
    // ...
    for (int i = 1; i < T; i++) {
        // 初始化 DP 数组
        // dp[j] = j 表示如果不进行买卖，j 元本金明天还是 j 元（相当于持有现金）
        for (int j = 0; j <= ans; j++) {
            dp[j] = j;
        }

        // 遍历每一种纪念品
        for (int k = 1; k <= N; k++) {
            int cost = prices[i][k];       // 今天买入的价格 (花费)
            int val = prices[i + 1][k];    // 明天卖出的价格 (收益)

            // 只有当明天涨价时，才考虑买入
            // 如果明天跌了或平价，不买肯定比买更划算（或者一样），直接跳过
            if (val > cost) {
                // 完全背包核心代码：正序遍历
                // j 代表当前假设持有的本金
                for (int j = cost; j <= ans; j++) {
                    // 状态转移方程：
                    // 不买这个：dp[j]
                    // 买这个：dp[j - cost] + val
                    dp[j] = max(dp[j], dp[j - cost] + val);
                }
            }
        }

        // 这一轮交易结束后，dp[ans] 就是明天手里能有的最大金币数
        // 更新本金，进入下一轮
        ans = dp[ans];
    }

    cout << ans << endl;

    return 0;
}

关键点解释

• 初始化 dp[j] = j：这很重要。这代表了一种“什么都不买，保留现金”的选择。如果所有商品第二天都跌价了，DP 也就不会更新，最后 dp[ans] 还是 ans，符合逻辑。
• 完全背包正序遍历：for (int j = cost; j <= ans; j++) 是完全背包的标志，意味着一个物品可以被多次选中。
• 空间复杂度：$O(M_{max})$，其中 $M_{max} \approx 10000$，内存占用极小。
• 时间复杂度：$O(T \times N \times M_{max})$。代入最大值计算约为 $100 \times 100 \times 10000 = 10^8$ 次运算。在 C++ 中，1秒内处理 $10^8$ 次简单加法运算是可以接受的（且实际数据很难跑满所有上界），因此不会超时。

你好！我是你的OI教练。

这道题（CSP-J 2019 T2 纪念品）是一道非常经典的动态规划（DP）题目，同时也结合了一些贪心的思想。

很多同学刚看到这道题会被“无限次买卖”、“当天买当天卖”、“T天N种商品”绕晕。别急，我们来把复杂的问题拆解开。

以下是解题的几个关键思路提示：

1. 核心思维转换：如何化繁为简？

题目中有一句很关键的话：“当日购买的纪念品也可以当日卖出”。 这看似是一句废话，其实暗示了一个极其重要的性质：

• 如果你想把一个纪念品从第 1 天持有到第 3 天，这等价于：第 1 天买入，第 2 天卖出；然后第 2 天立刻再买入，第 3 天卖出。

这意味着，我们不需要去考虑“跨越多天”的复杂策略。我们可以把整个过程切分成 $T-1$ 轮独立的交易：

• 第 1 天买，第 2 天卖，赚一笔钱。
• 拿着第 2 天手里所有的钱，作为本金，决定第 2 天买什么，第 3 天卖。
• ……
• 直到第 $T-1$ 天买，第 $T$ 天卖。

结论：我们只需要关注相邻两天（今天和明天）如何利用手中的钱赚最多的差价。

2. 每天的任务是什么？（数学模型）

假设我们现在处于第 $i$ 天，要把手里的钱换成商品，等到第 $i+1$ 天卖掉。 对于第 $j$ 种纪念品：

• 成本（花费）：第 $i$ 天的价格 $P_{i, j}$。
• 收益（价值）：第 $i+1$ 天的价格 $P_{i+1, j}$。
• 净利润：$P_{i+1, j} - P_{i, j}$。

我们的目标是：用手里现有的钱（本金），去购买若干个纪念品，使得“第 $i+1$ 天卖出后的总钱数”最大。

这听起来是不是很像一个经典的算法模型？

• 你有一定的“容量”（手里的钱）。
• 每种商品有“消耗”（今天的价格）和“价值”（明天的价格）。
• 每种商品可以买无限个。

没错，这就是完全背包问题！

3. 动态规划设计

每一轮（从第 $i$ 天到第 $i+1$ 天）都是一次完全背包。

• 背包容量：你当前拥有的金币数量 $M$。
• 物品：$N$ 种纪念品。
  • 物品 $j$ 的重量（Weight）：$P_{i, j}$（今天的价格）
  • 物品 $j$ 的价值（Value）：$P_{i+1, j}$（明天的价格）
  • (注：或者你可以把价值定义为差价 $P_{i+1, j} - P_{i, j}$，最后再加上本金，效果是一样的)
• 状态定义： dp[k] 表示花费 k 元成本，在第 $i+1$ 天能换回的最大价值（卖出的钱）。

4. 算法流程框架

1. 读取输入。
2. 外层循环：遍历每一天，从第 1 天到第 $T-1$ 天。
   • 在每一轮开始前，根据今天的价格和明天的价格，构建背包问题。
   • 如果明天的价格比今天低，这个商品这轮肯定不买（亏本），直接跳过。
   • 清空/重置 dp 数组（注意范围）。
   • 进行完全背包 DP 计算。
   • 背包容量是你当前手里拥有的金币数。
   • DP 结束后，dp[当前金币数] 就是你这一轮操作后，明天手里的总金币数。
   • 更新你的本金：将 dp 的结果作为下一轮的本金。
3. 循环结束后的本金就是答案。

5. 避坑指南

1. 数组大小：注意看数据范围，虽然初始金币 $M \le 1000$，但在交易过程中，金币数量会增加。虽然题目提示里有一句关于 $10^4$ 的说明，但为了保险，DP 数组要开得足够大以容纳可能的最大金币数（根据经验，通常开到 $10000$ 左右或者根据题目实际给出的最大可能金额来估算，这道题数据较弱，一般 $10000$ 或 $20000$ 足够）。
2. 完全背包的写法： dp[j] = max(dp[j], dp[j - cost] + value) 注意循环顺序，完全背包是从小到大枚举容量。
3. 贪心判断：如果 $P_{i+1, j} \le P_{i, j}$，也就是明天降价或者价格不变，那今天绝对不要买这个东西持有过夜，直接无视它。

加油！按照完全背包的思路去写，这道题就迎刃而解了。