P5662 [CSP-J2019] 纪念品 题解

· · 题解

原题链接：https://www.luogu.com.cn/problem/P5662。

更好的使用方式：https://www.luogu.com.cn/article/sxhfnpo8。

警告：严禁抄袭。

分析

这道题已知 N 件物品未来 T 天的价格，需要通过交易来让手中的 M 没金币尽可能变多，并且交易不限次数且没有手续费。

先看数据范围：

对于 T = 1 的 10 分，因为只有一天，所以每件物品只有一件价格，无论进行多少次买卖，钱都不会变多。因此 T = 1 时直接输出 M 即可。

对于 N = 1 的 15 分，只有一件商品，那么只要明天比今天贵，今天应该能买多上就买多少。因为明天可以直接全部卖掉，这样就实现了赚钱最大化，然后再考虑明天是否重新买回。

由 N = 1 的结论进一步总结得出，对于每一天的每件物品，就是使用当前的价格赚取今明两天的差价。之实际上是一个完全背包问题的模型，每天都是一轮完全背包问题。每一天手中的金币为背包的体积，每件物品的体积就是物品当天的价格，每件物品的价值就是当天与次日的价格差，这样做一次完全背包就能计算出来每天最多能赚多少钱。程序的时间复杂度是 O(NMT)。

AC代码

#include<bits/stdc++.h>
using namespace std;
int t, n, m;
int a[105][105];//a[i][j]：第i天，j号物品的价格
int f[10005];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t >> n >> m;
    for (int i = 0; i < t; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    //一天一天做，比较今天与明天
    for (int i = 0; i < t - 1; i++) {
        memset(f, 0, sizeof(f));
        for (int j = 0; j < n; j++) {
            if (a[i + 1][j] > a[i][j]) {
                //体积：a[i][j],价值：a[i + 1][j] - a[i][j]
                for (int k = a[i][j]; k <= m; k++) {
                    f[k] = max(f[k], f[k - a[i][j]] + a[i + 1][j] - a[i][j]);
                }
            }
        }
        //每一件物品考虑完后，f[m]即m元最多赚的钱
        m += f[m];
    }
    cout << m;
    return 0;
}

AC记录：https://www.luogu.com.cn/record/196364812。