完全背包

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

int main() {

    int T, N, M;
    cin >> T >> N >> M;
    // P[i][j] 存储第 i 天第 j 种纪念品的价格
    // 题目中 T <= 100, N <= 100
    vector<vector<int>> P(T + 1, vector<int>(N + 1));

    for (int i = 1; i <= T; ++i) {
        for (int j = 1; j <= N; ++j) {
            cin >> P[i][j];
        }
    }
    int cm = M;
    // 从第 1 天过渡到第 T 天，一共进行 T-1 轮交易决策
    // 第 k 轮决策：利用第 k 天的价格买入，利用第 k+1 天的价格卖出
    for (int day = 1; day < T; ++day) {
        // 完全背包 DP
        // dp[v] 表示：如果在第 day 天花费 v 元买入纪念品，
        // 到第 day+1 天卖出后，最多能换回多少钱。   
        // 背包容量上限是当前的钱数
        vector<int> dp(cm + 1);

        // 初始化：如果不买任何纪念品，直接持有现金，价值不变
        // 这相当于有一种“现金纪念品”，成本1，价值1
        for (int v = 0; v <= cm; v++) {
            dp[v] = v;
        }

        // 遍历 N 种纪念品，尝试买入
        for (int j = 1; j <= N; ++j) {
            int cost = P[day][j];     // 今天的买入价（成本）
            int value = P[day+1][j];  // 明天的卖出价（价值）

            // 完全背包：正序遍历容量
            // 只有当当前钱数 v 足够买得起这个纪念品时才尝试
            for (int v = cost; v <= cm; ++v) {
                // 状态转移：
                // 方案1：不买这个纪念品，保持 dp[v]
                // 方案2：买一个这个纪念品，花费 cost，获得 value，剩余的钱 v-cost 继续最优投资
                dp[v] = max(dp[v], dp[v - cost] + value);
            }
        }

        // 更新手中的金币数为这一天操作后的最大收益
        // 也就是 dp 数组在容量为 cm 时的最大值
        cm = dp[cm];
    }

    cout << cm << endl;

    return 0;
}