股票买卖问题 纪念品 2019CSP-J普及组C题 DP学习

中间一度怀疑是牛客的测评机出问题了……才发现是自己的数组越界。
太艰难了。
https://ac.nowcoder.com/acm/contest/2340/C
题目是比较简单的，思路大概就是求解第一天到第t-1天的最佳策略，所以大概也可以说是一道贪心的题目。
那么怎么确定最佳策略呢——填表。每个纪念品都会覆盖到某个值下的最优解，并且可以使得后续可以直接调用其生成的最优解，最后推出m对应的生成价值。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+5;
int main() {
    int a[105][105];
    int val[N]= {0};
    int t,n,m;
    cin>>t>>n>>m;
    for(int i=0; i<t; i++)
        for(int j=0; j<n; j++)
            cin>>a[i][j];
    t--;//最后一天直接卖掉 所以不算 我就是这里傻到然后数组越界（讲道理我置零了）（算了无所谓了
    for(int i=0; i<t; i++) {//遍历每一天
        memset(val,0,sizeof(val));
        for(int j=0; j<n; j++)//遍历每一个商品
            for(int k=a[i][j]; k<=m; k++)
                val[k]=max(val[k],a[i+1][j]-a[i][j]+val[k-a[i][j]]);
                //当天可以收割的最高价值
        m+=val[m];
    }
    cout<<m<<endl;
    return 0;
}

for(int k=a[i][j]; k<=m; k++)
                val[k]=max(val[k],a[i+1][j]-a[i][j]+val[k-a[i][j]]);

我总觉得这一块效率太低了，居然是一个一个填进入，而且每一位都要调用一次max函数，总觉得有更优的方案。
这个方案生成了大量的无用数据，如果数据覆盖范围广的话还好说，就只有两三个值的时候很多数据都是无效的。
挖坑again。顺便吐槽马上学校又要开网课了，致命的高数下，而且我下学期课又多，天知道还有没有时间填坑……

有一种绥靖政策的优化：如果明天降价就不考虑了

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int t,n,m,a[105][105],dp[10005];
int main() {
    int i,j,k;
    cin>>t>>n>>m;
    for(i=1; i<=t; i++) 
        for(j=1; j<=n; j++) 
            scanf("%d",&a[i][j]);
    for(i=1; i<t; i++) {
        memset(dp,0,sizeof(dp));
        for(j=1; j<=n; j++) {
            if(a[i][j]>=a[i+1][j]) continue;
            for(k=a[i][j]; k<=m; k++) 
                dp[k]=max(dp[k],dp[k-a[i][j]]+a[i+1][j]-a[i][j]);
        }
        m=m+dp[m];
    }
    cout<<m;
    return 0;
}

写到这里就越来越觉得是贪心了，那么是怎么解决“放长线钓大鱼”的问题的呢？

画了一下曲线，发现根本不存在“放长线钓大鱼”的问题，贪心永远是对的，因为信息是完全的，晚买永远是没问题的，计算每一天的收益就是最高收益。