贪心+dp

贪心：

对于一个物品的一次交易，我们会在第a天买入，第b天卖出，获益等于price[b]-price[a]。这个过程可以等效成在第a天买入，第a+1天卖出，第a+1天买入，第a+2天卖出，第a+2天买入，…，第b天卖出。由于这个方案可以覆盖所有方案，所以也一定可以覆盖最优解中。

对于一种物品连续持有若干天，可以看做第一天买入，第二天上午卖掉，然后第二天下午买回来，第三天上午卖掉，然后第三天下午买回来……最后一天卖出。所以我们就不需要记录每天手里持有多少纪念品了，统一认为我们今天买的物品，明天上午就全部卖掉，再买回部分商品。明天又是新的一天，用所有的现金，进行新的决策就好了。
这样做的正确性就是：在最优解中，我们进行一次交易一定是在a天买入，b天卖出，且a到b的每一天，商品的价格都是递增的，那么我们就可以把price[b]-price[a]的收益分散成a到b每一天的收益。这就说明不会因为一件商品第二天降价我们的方法会选择不买入从而把它忽略了。
dp：
对于第i天到第i+1天的可以赚到的最多差价是第i天拥有的钱m，买商品价格不超过m，每次买一个商品的收益是prime[i+1]-prime[i]。
这个过程就是完全背包了。

时间复杂度

$O(tnm)$

参考文献

yxc：https://www.acwing.com/solution/content/6407/

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
const int N=110,M=10010;
int w[N][N],f[M];
int main(){
    int t,n,m;
    cin>>t>>n>>m;
    for(int i=0;i<t;++i){
        for(int j=0;j<n;++j){
            cin>>w[i][j];
        }
    }
    for(int i=0;i<t-1;++i){
        memset(f,0,sizeof f);
        for(int j=0;j<n;++j){
            if(w[i+1][j]>w[i][j])
                for(int k=w[i][j];k<=m;++k){
                    f[k]=max(f[k],f[k-w[i][j]]+w[i+1][j]-w[i][j]);
                }
        }
        m+=f[m];
    }
    cout<<m<<endl;
    return 0;
}