题目描述
题目大意
在 \(T\) 天内，有 \(n\) 种纪念品和初始的 \(m\) 元。可以得到每天每种纪念品的价格。每一天可以以当日价格买卖纪念品。
特别的，当天卖出得到的钱可以当天买入，当日买入的纪念品也可以当日卖出。当然可以一直持有。
但是，\(T\) 天过后，手上不可以持有纪念品。
思路
分析这道题的算法，显而易见这是一道完全背包题
那么想要解决这道题，首先思考一个问题：
- 买入后什么时候卖出？这个问题可以利用反悔贪心的思想。举个例子，假设用三天的价格分别是 \(p_1\)、\(p_2\)、\(p_3\)，且\(p_1 < p_2 < p_3\)。那么如果在第1天买入，在第2天可以产生利润就卖出了，利润则为 \(p_2 - p_1\)，但其实在第三天买入时利润为 \(p_3 - p_1\)，会更优。这时候就可以在第1天买入，第2天依旧卖出，但不同的是第2天再次买入，第3天卖出，利润就会变为 \((p_2 - p_1) + (p_3 - p_2) = p_3 - p_1\)，就可以补足差价。
所以，这 \(t\) 天的买卖情况应该是：
$sb$
第1天：买入
第2天：卖出
完全背包
第2天：买入
第3天：卖出
完全背包
......
第t-1天：买入
第t天：卖出
完全背包
背包的三要素就是：容量，消耗，价值。
- 容量：当天持有的钱。
- 消耗：买入价，即今天价钱。
- 价值：卖出价，即明天价钱。
用完全背包的压维模版：
for (int i = 1; i <= n; i ++ )
for (int j = w[i]; j <= m; j ++ )
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
消耗 \(w_i\) 替换成今天价钱 \(p_{k, i}\)，价值 \(v_i\) 替换成明天价钱 \(p_{k+1, i}\)，容量 \(m\) 替换成当前持有的钱 \(ans\)。
其中 \(k\) 代表 第 \(k\) 天。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = 1e4 + 5;
int t, n, m;
int p[N][N];
int dp[M];
int main()
{
scanf("%d%d%d", &t, &n, &m);
for (int k = 1; k <= t; k ++ )
for (int i = 1; i <= n; i ++)
scanf("%d", &p[k][i]);
int ans = m; // 刚开始，持有m元
for (int k = 1; k < t; k ++ ) // 做t-1次完全背包
{
memset(dp, 0, sizeof dp); // 重置
// 完全背包压维模版：
for (int i = 1; i <= n; i ++ )
for (int j = p[k][i]; j <= ans; j ++ )
dp[j] = max(dp[j], dp[j - p[k][i]] + (p[k + 1][i] - p[k][i])); // (p[k + 1][i] - p[k][i]) 为 利润
ans += dp[ans]; // 加上盈利
}
printf("%d\n", ans); // 输出最终持有的钱数
return 0;
}