题解

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

const int N = 110, M = 1e4 + 10;
int w[N][N]; // w[t][i]：第 t 天第 i 种物品的价格
int dp[M]; // dp[j]：背包容量为 j 时的最大价值

int main() {

int T, n, m;  // 天数，纪念品个数，一开始的钱数 
cin >> T >> n >> m;
for(int t = 1; t <= T; t++) {  // T 天 
	for(int i = 1; i <= n; i++) {  // n 个纪念品 
		cin >> w[t][i];  // 第 t 天第 i 种物品的价格
	}
} 
for(int t = 1; t < T; t++) {  // T-1 天的完全背包
	memset(dp, 0, sizeof dp);  // 每天之前要初始化为 0 
	// 背包容量：钱 m，重量：w[t][i]，价值：w[t+1][i]-w[t][i] 
	for(int i = 1; i <= n; i++) {  // 枚举物品种数 
		for(int j = w[t][i]; j <= m; j++) {  // 枚举背包容量
			// dp[j] = max(dp[j], dp[j-w[i]] + v[i]); 
			dp[j] = max(dp[j], dp[j-w[t][i]] + (w[t+1][i]-w[t][i]));
		}
	}
	m += dp[m];  // 手里的钱 + 当天的收益：dp[m] 
}
cout << m;  // 在超能力消失后最多能拥有的金币数量

return 0;

}