[CSP-J 2019-T3]纪念品摘要本题是 2019 年 CSP-J 复赛的第三题考察算法为动态规划。核心突破口在于当日购买的纪念品也可以当日卖出这使得跨越多天的复杂交易可以被拆解为独立的相邻两天交易。每一天只需以前一天的金币数为背包容量以当天买入价、次日卖出价的差值为物品价值运行一个完全背包动态更新最大利润。多日累加后即可得到最终答案。核心考点完全背包建模 逐日贪心优化。题目描述小伟突然获得一种超能力他知道未来T TT天N NN种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量以及卖出一个该纪念品换回的金币数量。每天小伟可以进行以下两种交易无限次任选一个纪念品若手上有足够金币以当日价格购买该纪念品卖出持有的任意一个纪念品以当日价格换回金币。每天卖出纪念品换回的金币可以立即用于购买纪念品当日购买的纪念品也可以当日卖出换回金币。当然一直持有纪念品也是可以的。T TT天之后小伟的超能力消失。因此他一定会在第T TT天卖出所有纪念品换回金币。小伟现在有M MM枚金币他想要在超能力消失后拥有尽可能多的金币。输入格式第一行包含三个正整数T , N , M T, N, MT,N,M相邻两数之间以一个空格分开分别代表未来天数T TT纪念品数量N NN小伟现在拥有的金币数量M MM。接下来T TT行每行包含N NN个正整数相邻两数之间以一个空格分隔。第i ii行的N NN个正整数分别为P i , 1 , P i , 2 , … , P i , N P_{i,1},P_{i,2},\dots,P_{i,N}Pi,1​,Pi,2​,…,Pi,N​其中P i , j P_{i,j}Pi,j​表示第i ii天第j jj种纪念品的价格。输出格式输出仅一行包含一个正整数表示小伟在超能力消失后最多能拥有的金币数量。输入输出样例 #1输入 #16 1 100 50 20 25 20 25 50输出 #1305输入输出样例 #2输入 #23 3 100 10 20 15 15 17 13 15 25 16输出 #2217说明/提示样例 1 说明最佳策略是第二天花光所有100 100100枚金币买入5 55个纪念品1 11第三天卖出5 55个纪念品1 11获得金币125 125125枚第四天买入6 66个纪念品1 11剩余5 55枚金币第六天必须卖出所有纪念品换回300 300300枚金币第四天剩余5 55枚金币共305 305305枚金币。超能力消失后小伟最多拥有305 305305枚金币。样例 2 说明最佳策略是第一天花光所有金币买入10 1010个纪念品1 11第二天卖出全部纪念品1 11得到150 150150枚金币并买入8 88个纪念品2 22和1 11个纪念品3 33剩余1 11枚金币第三天必须卖出所有纪念品换回216 216216枚金币第二天剩余1 11枚金币共217 217217枚金币。超能力消失后小伟最多拥有217 217217枚金币。数据规模与约定对于10 % 10\%10%的数据T 1 T 1T1。对于30 % 30\%30%的数据T ≤ 4 , N ≤ 4 , M ≤ 100 T \leq 4, N \leq 4, M \leq 100T≤4,N≤4,M≤100所有价格10 ≤ P i , j ≤ 100 10 \leq P_{i,j} \leq 10010≤Pi,j​≤100。另有15 % 15\%15%的数据T ≤ 100 , N 1 T \leq 100, N 1T≤100,N1。另有15 % 15\%15%的数据T 2 , N ≤ 100 T 2, N \leq 100T2,N≤100。对于100 % 100\%100%的数据T ≤ 100 , N ≤ 100 , M ≤ 10 3 T \leq 100, N \leq 100, M \leq 10^3T≤100,N≤100,M≤103所有价格1 ≤ P i , j ≤ 10 4 1 \leq P_{i,j} \leq 10^41≤Pi,j​≤104数据保证任意时刻小伟手上的金币数不可能超过10 4 10^4104。思路要点这道题其实就是一个“知道未来物价的倒爷模拟器”。 核心突破口在于题目的一句话当日购买的纪念品也可以当日卖出。 这意味着我们在第 1 天买入第 3 天卖出其实等价于第 1 天买入第 2 天卖出。第 2 天再买回来第 3 天再卖出。通过这个思路我们可以将连续多天的复杂买卖全部拆解为独立的“相邻两天”的交易。我们每一天只需要考虑一件事用手头现有的金币在今天买什么东西明天卖掉能赚最多关键思路根据题意每个物品可以无限次购买那么每一天除了最后一天我们面临的其实是一个完全背包问题背包容量今天手上的总金币数M MM。物品重量物品今天的买入价格a i , j a_{i,j}ai,j​。物品价值利润物品明天的价格减去今天的价格a i 1 , j − a i , j a_{i1,j} - a_{i,j}ai1,j​−ai,j​。如果利润为负或零直接跳过不买。状态转移方程设d p [ k ] dp[k]dp[k]为花费k kk枚金币能获得的最大利润:d p [ k ] max ⁡ ( d p [ k ] , d p [ k − a i , j ] a i 1 , j − a i , j ) dp[k] \max(dp[k], dp[k - a_{i,j}] a_{i1,j} - a_{i,j})dp[k]max(dp[k],dp[k−ai,j​]ai1,j​−ai,j​)每一天结束后将最大利润加到本金上M M d p [ M ] M M dp[M]MMdp[M]然后带着新的M MM进入下一天的循环。解题步骤我们以输入样例 2为例模拟代码的执行过程。3 3 100 10 20 15 15 17 13 15 25 16变量定义与初始化定义全局变量int t, n, m, a[105][105], f[10005];。t 3天数n 3物品数m 100初始金币。数组a存下了 3 天 3 种物品的价格。核心循环模拟我们来模拟外层循环第一轮即处理第 1 天向第 2 天过渡的过程此时i 1 i 1i1清空背包 执行memset(f, 0, sizeof(f));将上一天的状态清空。此时f数组所有元素均为 0。处理第 1 个纪念品(j 1 j 1j1)第 1 天价格为 10第 2 天价格为 15。计算利润p 15 − 10 5 p 15 - 10 5p15−105。利润大于 0可以赚钱内层循环容量k kk从 10 遍历到 100当前金币数当k 10时f[10] max(f[10], f[0] 5) 5当k 20时f[20] max(f[20], f[10] 5) 10因为是正向循环这里用到了刚更新的f[10]代表可以重复买体现了完全背包……当k 100时f[100] 50手里的 100 金币全部买入 10 个商品 1能赚 50。处理第 2 个纪念品(j 2 j 2j2)第 1 天价格为 20第 2 天价格为 17。计算利润p 17 − 20 − 3 p 17 - 20 -3p17−20−3。小于等于 0触发if(a[i 1][j] a[i][j]) continue;直接跳过。处理第 3 个纪念品(j 3 j 3j3)第 1 天价格为 15第 2 天价格为 13。计算利润p 13 − 15 − 2 p 13 - 15 -2p13−15−2。小于等于 0直接跳过。更新金币总数第一天买卖结束执行m f[m];。此时m 100 f[100] 100 50 150。随后循环进入下一天i 2 i 2i2第 2 天向第 3 天过渡此时的背包容量总金币数已经滚雪球变成了150继续重复上面的背包决策。本题易错点坑一忘记清空 DP 数组要点提醒每天的交易必须是重新开始计算利润的。如果不写memset(f, 0, sizeof(f));会导致前一天的状态污染今天的计算。坑二数组开得不够大要点提醒本题中说小伟手上的金币数不可能超过 10000。有同学看到M 1000就只把 f 数组开到 1005但实际在多天累加后 M 是会增长的。一定要根据题目提示的“最大可能金币数”来开数组。坑三循环顺序写反要点提醒因为每种物品可以买无限次这是完全背包内层循环k必须是正序从小到大遍历。如果写成了倒序就变成了只能买一次的 01 背包。参考代码#includebits/stdc.husingnamespacestd;intt,n,m;inta[105][105];// a[i][j] 表示第 i 天第 j 种纪念品的价格intf[10005];// f[k] 表示花费 k 枚金币能够赚取的最大利润intmain(){scanf(%d %d %d,t,n,m);// 读入每天每种物品的价格for(inti1;it;i){for(intj1;jn;j){scanf(%d,a[i][j]);}}// 核心逻辑枚举前 t-1 天每次计算今天买入、明天卖出的最大利润for(inti1;it;i){memset(f,0,sizeof(f));// 每天的交易都是独立的必须清空 DP 数组for(intj1;jn;j){// 优化如果明天卖不上好价钱亏本或不赚钱直接跳过不买if(a[i1][j]a[i][j])continue;// 完全背包核心转移正序遍历容量代表同一件物品可以被重复购买for(intka[i][j];km;k){intpa[i1][j]-a[i][j];// p 为买入 a[i][j] 赚到的利润f[k]max(f[k],f[k-a[i][j]]p);}}// 今天的本金 赚到的最大利润 明天的本金mf[m];}printf(%d\n,m);return0;}背包问题小结第一步翻译核心三要素代价、价值、容量先分清题目里谁是花费cost谁是收益val谁是总限制V。比如纪念品这题代价是今天的价格价值是明天的利润容量是今天的本金。第二步写死外层循环提取变量外层永远是遍历物品种类或者天数、阶段。for(inti1;in;i){intcost...;// 明确写出代价是什么intval...;// 明确写出价值是什么}建议不要在内层循环的状态转移方程里写一大堆。用明确的变量名例如cost和val替换带有复杂下标的二维数组比如本题的a[i1][j] - a[i][j]能减少大脑的内存占用。第三步靠口诀写内层循环容易错的地方01 背包每件只能买一次倒序遍历容量。for (int j V; j cost; j--)完全背包每件能买无限次正序遍历容量。for (int j cost; j V; j)转移方程永远是这句dp[j] max(dp[j], dp[j - cost] val);