[原题传送门](https://www.luogu.com.cn/problem/P5662 "原题传送门") ### 思路 DP ### 代码 ```csharp #include<bits/stdc++.h> using namespace std; const int N = 101; const int M = 10001; int n, m, t, price[N][N], f[M]; int main(){ scanf("%d%d%d",&t,&n,&m); for(int i = 1; i <= t; i++) for(int j = 1; j <= n; j++) scanf("%d",&price[j][i]); //读入每种商品每天的价格 for(int k = 1; k < t; k++){ memset(f, 0, sizeof f);//每轮开始前都要初始化为0 for(int i = 1; i <= n; i++) for(int j = price[i][k]; j <= m; j++)//完全背包 f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]); m += f[m];//加上最大差价，更新手里有的钱 } printf("%d",m); return 0; } ```