洛谷P5662题解

原题链接：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。