洛谷
小伟突然获得一种超能力，他知道未来 T 天 N 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。
每天，小伟可以进行以下两种交易无限次：
- 任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；
- 卖出持有的任意一个纪念品，以当日价格换回金币。
每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。
T 天之后，小伟的超能力消失。因此他一定会在第 T 天卖出所有纪念品换回金币。
小伟现在有 M 枚金币，他想要在超能力消失后拥有尽可能多的金币。
输入格式
第一行包含三个正整数 T,N,M，相邻两数之间以一个空格分开，分别代表未来天数 T，纪念品数量 N，小伟现在拥有的金币数量 M。
接下来 T 行，每行包含 N 个正整数，相邻两数之间以一个空格分隔。第 i 行的 N 个正整数分别为 Pi,1,Pi,2,…,Pi,N，其中 Pi,jPi,j 表示第 i 天第 j 种纪念品的价格。
输出格式
输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。
如果只有一天，买入又卖出，答案等于输入。
如果有两天，问题转化成，给定一些物品的成本和收益，求出如何购买使得收益最大，这是一个典型的完全背包问题。
但是如果有t天，可以当成t-1次完全背包。
因为一天可以同时进行买入和卖出，进入到新的一天中可以先全部卖出，（背包的容量一定单调不减），然后再买入到对应的数量。这和仅对于某些物品进行增加或减少（最优方案）的效果是一样的。但是全部卖出后重新买入通过完全背包一定能得到最优解。
第i次的体积是第i天的买入价格，价值是明天和今天的差价。
反正如果本来不该卖的就重新买入即可。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define DBG
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rrep(i,b,a) for(int i=(b);i>=(a);i--)
#ifdef DBG
#define dbg(...) (cout<<":D ",_((char*)#__VA_ARGS__,__VA_ARGS__))
template<typename t> void _(char* p,t x){cout<<p<<'='<<x<<'\n';}
template<typename t,typename... a>
void _(char* p,t x,a... y){while(*p!=',')cout<<*p++;cout<<'='<<x<<',';_(p+1,y...);}
#else
#define dbg(...) ((void)0)
#endif
int dp[105][10010];
int a[110][110];
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
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 k = 1; k <= T - 1; k++) {
for (int i = 1; i <= N; i++) {
int w = a[k][i], v = a[k+1][i] - a[k][i]; //
for (int j = 1; j <= M; j++) {
dp[i][j] = dp[i-1][j];
if (j - w < 0) {
continue;
}
dp[i][j] = max(dp[i][j],dp[i][j-w] + v);
}
}
M = dp[N][M] + M;
//memset(dp,0,sizeof(dp));
}
cout << M << endl;
return 0;
}