CSP-J2019普及组复赛T3—— 纪念品

题目描述

小伟突然获得一种超能力，他知道未来 T 天 N 种纪念品每天的价格。

某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。

每天，小伟可以进行以下两种交易无限次：

任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品，注意同一个纪念品可以在同一天重复买； 卖出持有的任意一个纪念品，以当日价格换回金币。 每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。

当然，一直持有纪念品也是可以的。

T 天之后，小伟的超能力消失。

因此他一定会在第 T 天卖出所有纪念品换回金币。

小伟现在有 M 枚金币，他想要在超能力消失后拥有尽可能多的金币。

输入格式

第一行包含三个正整数 T,N,M，相邻两数之间以一个空格分开，分别代表未来天数 T，纪念品数量 N，小伟现在拥有的金币数量 M。

接下来 T 行，每行包含 N 个正整数，相邻两数之间以一个空格分隔。第 i 行的 N 个正整数分别为 $P_{i,1}，P_{i,2},\dots \dots ,P_{i,N}$，其中 $P_{i,j}$ 表示第 $i$ 天第$j$ 种纪念品的价格。

输出格式 输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。

输入样例

3 3 100 10 20 15 15 17 13 15 25 16

输出样例

217

算法思想

对任意一种纪念品来说，在第a天买入、第b天卖出，等价于第a天买入、第a+1天卖出、第a+1天买入、第a+2天卖出、…、最后在第b天卖出。

因此，任何一个交易方案都可以转换成一系列在某天买入、然后在隔天卖出的方案，即时间跨度为1天的方案集合。最优解也不例外。

这样，就可以枚举每一天的交易方案，因为今天的买入的纪念品一定在隔天全部卖出，不会影响后面的结果。

如果初始金币为M，目标是让第二天的金币数尽可能多，再让第三天的金币数尽可能多；…。这里是一个明显的贪心策略。

如果第$i$天的金币数量为$M_i$，要让第$i+1$天的金币数量$M_{i+1}$尽可能多，即在求金币数量不超过$M_i$的情况下，可以获得的最大收益，且每件纪念品可以买卖任意多个，这是一个完全背包问题。

算法实现

遍历从1到t-1的每一天k在第k天，通过完全背包计算出当天前n件物品在金币数为m的情况下的最大收益f[m]将最大收益累加至m，即算出到第k+1天时的总金币数。重复1、2、3就计算出到第t天的总金币数。

时间复杂度

$O(T\times n\times m)=10^8$

代码实现

#include <iostream> #include <cstring> using namespace std; const int N = 110, M = 10100; int w[N][N]; //f[M]表示在金币数不超过M的情况下的最大收益 int f[M]; int main() { int t, n, m; cin >> t >> n >> m; //输入n件物品每天的价格 for(int i = 1; i <= t; i ++) for(int j = 1; j <= n; j ++) cin >> w[i][j]; for(int k = 1; k < t; k ++) { memset(f, 0, sizeof f); // 每天都要初始化f[] for(int i = 1; i <= n; i ++) { if(w[k + 1][i] > w[k][i]) //优化，只考虑第k + 1天价格高于第k天价格的情况 { for(int j = w[k][i]; j <= m; j ++) { //第k天扣除一件i纪念品的最大收益，加上这件纪念品在第k+1天的收益 f[j] = max(f[j], f[j - w[k][i]] + w[k + 1][i] - w[k][i]); } } } m += f[m]; //将当天的最大收益累加到总金币数中 } cout << m << endl; return 0; }