第六周第七题题目解析

问题本质

看似复杂的多天多物品交易问题，核心转化为 T−1 轮完全背包。

思路分析

关键洞察：相邻天拆分

因为同一天可以先卖后买，所以持有一个物品从第 1 天到第 3 天，等价于：

第 1 天买 → 第 2 天卖 → 第 2 天立刻买回 → 第 3 天卖

中间那次"卖了又买"净收益为 0，不影响结果。因此：

跨多天的持有，可以拆成若干"相邻两天"的独立交易。

转化为完全背包

对于每一对相邻天 $(i, i+1)$，问题变成：

• 背包容量 = 当前金币数 M
• 物品 j：
  • 花费（买入价）= $P[i][j]$
  • 收益（利润）= $P[i+1][j] - P[i][j]$（仅当 > 0 时有意义）
• 每种物品可以买无限个 → 完全背包
• 做完一轮背包后，M += 最大利润，进入下一天

样例 1 验证

6 天 1 种纪念品，M=100，价格：50, 20, 25, 20, 25, 50

相邻天	买入价	卖出价	利润	操作
1→2	50	20	−30	不买
2→3	20	25	+5	买 5 个，赚 25，M=125
3→4	25	20	−5	不买
4→5	20	25	+5	买 6 个（花 120），赚 30，M=155
5→6	25	50	+25	买 6 个（花 150），赚 150，M=305

wait — 让我重新用背包思路逐步算：

• 初始 M=100
• 第 2→3 天：容量 100，物品花费 20 利润 5 → 买 5 个赚 25 → M=125
• 第 4→5 天：容量 125，物品花费 20 利润 5 → 买 6 个赚 30（剩 5 coin）→ M=155
• 第 5→6 天：容量 155，物品花费 25 利润 25 → 买 6 个赚 150（剩 5 coin）→ M=305

代码（逐行注释版）

#include <bits/stdc++.h>
using namespace std;

int price[101][101];          // price[i][j] = 第 i 天第 j 种纪念品的价格
int dp[10001];                // 完全背包数组，dp[j] = 容量 j 时的最大利润

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

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

    // 读入价格表
    for (int i = 1; i <= T; i++)
        for (int j = 1; j <= N; j++)
            cin >> price[i][j];

    // 对每一对相邻天，做一次完全背包
    for (int day = 1; day < T; day++) {

        // 清空 dp 数组
        memset(dp, 0, sizeof(dp));

        // 完全背包：每种纪念品可以买无限个
        for (int j = 1; j <= N; j++) {
            int cost = price[day][j];                  // 买入价（第 day 天）
            int profit = price[day + 1][j] - cost;     // 利润 = 明天卖 - 今天买

            if (profit <= 0) continue;                 // 不赚钱的不买

            // 完全背包核心：正序遍历（允许同一物品买多次）
            for (int c = cost; c <= M; c++) {
                dp[c] = max(dp[c], dp[c - cost] + profit);
            }
        }

        M += dp[M];   // 当前金币 += 最大利润，带入下一天
    }

    cout << M << endl;
    return 0;
}

复杂度

• 时间：$O(T \times N \times M_{max})$，最坏 $100 \times 100 \times 10000 = 10^8$，每步仅比较和加法，C++ 1s 可过
• 空间：$O(M_{max})$ = 10001 个 int ≈ 40KB

核心要点速记

本题的精髓是两步转化：

1. 多天 → 相邻两天：因为同天可卖可买，跨天持有可拆成逐天交易

2. 相邻两天交易 → 完全背包：花费 = 今天买入价，价值 = 明天卖出利润，每种可买无限个

完全背包 vs 0-1 背包的区别只在遍历方向：

• 0-1 背包（每种 1 个）→ 倒序

• 完全背包（每种无限）→ 正序

---