思路加题解

题目大意

未来有 T 天，每天可以无限次买入或卖出任意一种纪念品。
初始有 M 枚金币。
每天买入和卖出的价格是相同的。
第 T 天必须将手中所有纪念品卖出，换回金币。
目标是最大化第 T 天结束时的金币总数。

关键点:

交易可以无限次进行，意味着我们可以在一天内买入、卖出、再买入……
每次交易利润 = 卖出价 - 买入价，所以我们可以把问题转化为在相邻两天之间寻找“差价”并进行“套利”。
因为可以在一天内无限次交易，所以我们可以将问题简化为在每一天与下一天之间进行“最大套利”操作。

解题思路（贪心 + 多重背包）
我们可以将问题拆解为：
对于每一天 i（从第1天到第 T-1 天），我们考虑从第 i 天到第 i+1 天之间的交易。
对于每种纪念品 j，如果 P[i+1][j]>P[i][j] ，则我们可以买入第 i 天的纪念品，在第 i+1 天卖出，获得差价利润。
所以每一天可以看作是一个多重背包问题，即我们用当前的金币，尽可能多地买入那些“明天价格更高”的纪念品，然后在第二天卖出，获得利润。

算法选择

对于每一天 i，我们构建一个“套利背包”：
每个物品的“成本”是 P[i][j]，收益是 P[i+1][j] - p[i][j]
我们的目标是用当前的金币尽可能多地买入这些“有利可图”的纪念品
使用完全背包模型（因为每个纪念品可以无限买入）
每天更新金币数为：当前金币 + 最大利润
三、信奥知识教授
与信奥相关的知识点
完全背包问题：每个物品可以选无限次，适合本题“无限次交易”的设定。
状态压缩与动态规划：每天的状态只依赖前一天，可以用滚动数组优化空间。

贪心思想：只关注有正利润的交易机会。
时间复杂度分析：最多 T=100 天，每种纪念品价格最大为 10^4
，金币最大为 10^4
，所以每轮背包复杂度是 O(MN)，总复杂度 O(TMN) 是可以接受的。

正解：

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

const int MAXM = 10000 + 5;
int T, N, M;
int price[105][105];  // price[i][j] 表示第i天第j种纪念品的价格

int main() {
    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) {
        int dp[MAXM] = {0};  // 每天重新初始化 dp
        int profit = 0;
        for (int j = 1; j <= N; ++j) {
            int buy = price[day][j];
            int sell = price[day + 1][j];
            if (sell > buy) {  // 只考虑有利润的纪念品
                for (int k = buy; k <= M; ++k) {
                    dp[k] = max(dp[k], dp[k - buy] + (sell - buy));
                }
            }
        }
        M += dp[M];  // 当天的利润加到金币上
    }

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