55015 - [CSP-J2019]纪念品（souvenir）

解题思路

先考虑n=1的情况：相邻两天的价格差当作一个物，当然，price=a[i],value=a[i+1]-a[i]。

dp[i]表示花费i金币的不包括本金的最大收益。

同时选物品i和i+1收益就是a[i+2]-a[i]，每一天可以买卖多个，所以是完全背包。

注意：每天结束之后更新m，收益也可以用。

再考虑多个纪念品：每一天都有n个物品，每个物品的价格还是本身，收益是下一天的减这一天的价格。每一天把n个物品做完全背包，之后更新m，最后的m就是答案。

tips:不要忘记每天清空dp数组。

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[105][105], dp[10005];
int main() {
	int t, n, m; cin >> t >> n >> m;
    for (int i = 1; i <= t; ++i) { 
        for (int j = 1; j <= n; ++j) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= t; ++i) {
        memset(dp, 0, sizeof dp);
        for (int j = 1; j <= n; ++j) { 
            for (int k = a[i][j]; k <= m; ++k) {
            	dp[k] = max(dp[k], dp[k - a[i][j]] + a[i + 1][j] - a[i][j]);
            }
        }
        m = (dp[m] > 0) ? (dp[m] + m) : m;
    }
    cout << m << '\n';
    return 0;
}