自动搬运

查看原文

来自洛谷，原作者为

	泥土笨笨 《算法竞赛实战笔记》作者

搬运于2025-08-24 22:13:06，当前版本为作者最后更新于2019-11-17 15:05:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

看到题目就感觉到一定是动态规划了，但是怎么定义状态呢？到每一天的时候，手里不同纪念品的数量有很多，要是每种情况都存下来，状态爆炸多，必死无疑啊。

这题感觉跟买卖股票很像啊，回忆一下我平时怎么炒(pei)股(qian)的呢？就是频繁交易嘛，今天买了，明天看到涨就卖，看到跌了也忍不住要卖。可惜我没有小伟的超能力啊，这里实名羡慕。

这题题面有一句关键的话，“当日购买的纪念品也可以当日卖出换回金币”！这句话可以帮我们简化状态，因为如果一个纪念品，你想连续持有若干天，可以看做第一天买，第二天早上立刻卖掉，然后第二天买回来，第三天早上立刻卖掉，然后第三天买回来……所以我们就不需要记录每天手里持有多少纪念品了，统一认为我们今天买的纪念品，明天早上就立刻卖掉。明天又是新的一天，用所有的现金，进行新的决策就好了。

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

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

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

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

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

其余细节见代码注释：

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
const int MAXN = 105;

//dp[k]表示手里剩k元现金的时候，明天早上都卖了以后的钱数
//price[i][j]表示第i天第j件物品的价格
int dp[10005], price[MAXN][MAXN];

int main() {
    int t, n, m, ans;
    scanf("%d%d%d", &t, &n, &m);
    //先输入
    for (int i = 1; i <= t; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &price[i][j]);
        }
    }
    //第一天早上手里有m元
    ans = m;
    for (int i = 1; i < t; ++i) {
        //先把数组赋值为负无穷
        memset(dp, ~0x3f, sizeof(dp));
        //什么都不买，今天早上有ans元，明天早上也是ans元
        dp[ans] = ans;
        //枚举第j个物品
        for (int j = 1; j <= n; ++j) {
            //手里有k元的时候，去推明天早上的钱
            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 ma = 0;
        for (int j = 0; j <= ans; ++j) {
            ma = max(ma, dp[j]);
        }
        //明天早上就有这么多钱了，继续赚钱
        ans = ma;
    }
    cout << ans << endl;
    return 0;
}