题面
小伟突然获得一种超能力，他知道未来 \(T\) 天 \(N\) 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。每天，小伟可以进行以下两种交易无限次：
- 任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；
- 卖出持有的任意一个纪念品，以当日价格换回金币。 每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。
\(T\) 天之后，小伟的超能力消失。因此他一定会在第 \(T\) 天卖出所有纪念品换回金币。 小伟现在有 \(M\) 枚金币，他想要在超能力消失后拥有尽可能多的金币。
输入
第一行包含三个正整数 \(T,N,M\)，相邻两数之间以一个空格分开，分别代表未来天数 \(T\)，纪念品数量 \(N\)，小伟现在拥有的金币数量 \(M\)。 接下来 \(T\) 行，每行包含 \(N\) 个正整数，相邻两数之间以一个空格分隔。第 \(i\) 行的 \(N\) 个正整数分别为\(P_{i,1},P_{i,2},……,P_{i,N}\)，其中 \(P_{i,j}\) 表示第 \(i\) 天第 \(j\) 种纪念品的价格。
输出
输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。
题解
有限商品有限金钱，但每天可购入的商品都没有数量限制，一眼完全背包！……然而没写出来orz
纠结点：模板背包题中，物品同时具有两个属性：费用 \(cost\) 和价值 \(value\) ，而这道题中商品费用 = 价值。即使能想到商品的重量就是卖出价值 - 买进价值，但是因为无法确定具体哪一天卖出最佳，思路陷入死循环
本题破题关键点：当日购买的纪念品也可以当日卖出换回金币
这题题面有一句关键的话，“当日购买的纪念品也可以当日卖出换回金币”！这句话可以帮我们简化状态，因为如果一个纪念品，你想连续持有若干天，可以看做第一天买，第二天早上立刻卖掉，然后第二天买回来，第三天早上立刻卖掉，然后第三天买回来……所以我们就不需要记录每天手里持有多少纪念品了，统一认为我们今天买的纪念品，明天早上就立刻卖掉。明天又是新的一天，用所有的现金，进行新的决策就好了。
——P5662 纪念品 题解 - 泥土笨笨
所以本题中，商品的费用即为明天的价值 - 当天的价值，由此建立集合与状态转移方程：
集合：前 \(i\) 天的前 \(j\) 个物品，此时还有 \(k\) 枚金币；
属性：要求最终拥有的最多金币数量，也是能赚到的最大差价，即为最大价值问题。
划分方案：\(price[i][j]\) 表示第 \(i\) 天第 \(j\) 个物品的价格，对于第 \(i\) 天的第 \(j\) 种物品来说，若要，则比起前一天来说的现金少了 \(price[i][j]\) ，但是明天的收益则会多出可赚的差价。
朴素方程：\(f[i][j][k]=max(f[i][j][k],f[i][j-1][k+price[i][j]]+price[i+1][j]-price[i][j])\)
但是本题的数据规模是 \(t<=100,N<=100,M<=10^3\) ，三维数组时间空间都会炸，所以需要优化降维。
第一维天数在传递过程中只需要保留当天最大收益即可，所以可以优化掉；
第二维物品的优化参考完全背包问题即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int t, m, n;
int v[N][N], w[N][N], f[N * N];
int main()
{
cin >> t >> n >> m;
for (int i = 1; i <= t; i++) {
for (int j = 1; j <= n; j++) {
cin >> v[i][j];
w[i - 1][j] = v[i][j] - v[i - 1][j];
}
}
for (int d = 1; d < t; d++) {
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i++)
for (int j = v[d][i]; j <= m; j++)
f[j] = max(f[j], f[j - v[d][i]] + w[d][i]);
m += f[m];
}
cout << m;
}