问题标题: 酷町堂：在一个月黑风高的晚上....

5223

救救孩子吧 邪恶啊!

这道题是原题的魔改吗? 有没有大佬找找哪里被改了.... (等一个月吧...实在没人的话随便找一个采纳把豆送了,毕竟空放着挺可惜的,,,)

30分  7Runtime Error

#include <iostream>
#include <cstring>
using namespace std;
int dp[10010], price[110][110];
int main() {
    int t, n, m;
    cin >> t >> n >> m;
    for (int i=1; i<=t; i++)
        for (int j=1; j<=n; j++)
            cin >> price[i][j];
    int ans = m;
    for (int i=1; i<t; i++) {
        memset(dp, ~0x3f3f3f, sizeof(dp));
        dp[ans] = ans;
        for (int j=1; j<=n; j++) {
            for (int k=ans; k>=price[i][j]; k--) {
                dp[k-price[i][j]] = max(dp[k-price[i][j]], dp[k] + price[i+1][j] - price[i][j]);
            }
        }
        int maxn = 0;
        for (int j=0; j<=ans; j++) {
            maxn = max(maxn, dp[j]);
        }
        ans = maxn;
    }
    cout << ans;
    return 0;
}

缪鲲鹏在2020-07-21 19:31:47追加了内容

思路在这

定义一个三维的数组,dp[i][j][k]dp[i][j][k]表示第i天，我们考虑到第j个物品的时候，手里现金还有k元的时候，明天早上全卖掉能拿到的金币数。类似完全背包的思路，就可以写递推了。我们用price[i][j]price[i][j]表示第i天第j个物品的价格，外层循环i，里层循环每个物品j，手里留k元现金，则

dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k+price[i][j]]+price[i+1][j]-price[i][j])dp[i][j][k]=max(dp[i][j][k],dp[i][j−1][k+price[i][j]]+price[i+1][j]−price[i][j])

表示第j个物品如果要了，手里现金少了price[i][j]price[i][j]，但是期望明天早上的收益多了price[i+1][j]-price[i][j])price[i+1][j]−price[i][j])

j循环完一遍以后，在收益里面取最大值，变成下一天的开始金币数。

但是这样开三维数组会炸空间，没关系，见过世面的我根本不慌。因为从第i天传递到第i+1天，只需要传递一个数字，即最大收益。如果第二题早上都卖掉有多重选择，为啥不选最赚钱的呢，是吧？所以第一个维度可以压掉。第二个维度，多重背包可以循环的时候控制循环方向压一维，相信学过完全背包的同学都会。所以其实数组只有一维就够了，表示手里现金数，按照题目说明，不会超过10000

上述思路借鉴一位大神