CSP 真题解析：[CSP-J 2019-T3] 纪念品
[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
输入 #1
6 1 100 50 20 25 20 25 50输出 #1
305输入输出样例 #2
输入 #2
3 3 100 10 20 15 15 17 13 15 25 16输出 #2
217说明/提示
样例 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 = 1T=1。
对于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,N=1。
另有15 % 15\%15%的数据，T = 2 , N ≤ 100 T = 2, N \leq 100T=2,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_{i+1,j} - a_{i,j}ai+1,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_{i+1,j} - a_{i,j})dp[k]=max(dp[k],dp[k−ai,j]+ai+1,j−ai,j)
每一天结束后，将最大利润加到本金上：M = M + d p [ M ] M = M + dp[M]M=M+dp[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 = 1i=1）：
清空背包： 执行
memset(f, 0, sizeof(f));，将上一天的状态清空。此时f数组所有元素均为 0。处理第 1 个纪念品(j = 1 j = 1j=1)：
第 1 天价格为 10，第 2 天价格为 15。计算利润：p = 15 − 10 = 5 p = 15 - 10 = 5p=15−10=5。利润大于 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 = 2j=2)：
- 第 1 天价格为 20，第 2 天价格为 17。计算利润：p = 17 − 20 = − 3 p = 17 - 20 = -3p=17−20=−3。小于等于 0，触发
if(a[i + 1][j] <= a[i][j]) continue;，直接跳过。
- 第 1 天价格为 20，第 2 天价格为 17。计算利润：p = 17 − 20 = − 3 p = 17 - 20 = -3p=17−20=−3。小于等于 0，触发
处理第 3 个纪念品(j = 3 j = 3j=3)：
- 第 1 天价格为 15，第 2 天价格为 13。计算利润：p = 13 − 15 = − 2 p = 13 - 15 = -2p=13−15=−2。小于等于 0，直接跳过。
更新金币总数：第一天买卖结束，执行
m += f[m];。此时m = 100 + f[100] = 100 + 50 = 150。随后，循环进入下一天（i = 2 i = 2i=2，第 2 天向第 3 天过渡），此时的背包容量（总金币数）已经滚雪球变成了150，继续重复上面的背包决策。
本题易错点
坑一：忘记清空 DP 数组
要点提醒：每天的交易必须是重新开始计算利润的。如果不写
memset(f, 0, sizeof(f));，会导致前一天的状态污染今天的计算。坑二：数组开得不够大
要点提醒：本题中说小伟手上的金币数不可能超过 10000。有同学看到
M <= 1000就只把 f 数组开到 1005，但实际在多天累加后 M 是会增长的。一定要根据题目提示的“最大可能金币数”来开数组。坑三：循环顺序写反
要点提醒：因为每种物品可以买无限次，这是完全背包！内层循环
k必须是正序（从小到大）遍历。如果写成了倒序，就变成了只能买一次的 01 背包。
参考代码
#include<bits/stdc++.h>usingnamespacestd;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(inti=1;i<=t;i++){for(intj=1;j<=n;j++){scanf("%d",&a[i][j]);}}// 核心逻辑：枚举前 t-1 天，每次计算今天买入、明天卖出的最大利润for(inti=1;i<t;i++){memset(f,0,sizeof(f));// 每天的交易都是独立的，必须清空 DP 数组for(intj=1;j<=n;j++){// 优化：如果明天卖不上好价钱（亏本或不赚钱），直接跳过不买if(a[i+1][j]<=a[i][j])continue;// 完全背包核心转移：正序遍历容量，代表同一件物品可以被重复购买for(intk=a[i][j];k<=m;k++){intp=a[i+1][j]-a[i][j];// p 为买入 a[i][j] 赚到的利润f[k]=max(f[k],f[k-a[i][j]]+p);}}// 今天的本金 + 赚到的最大利润 = 明天的本金m+=f[m];}printf("%d\n",m);return0;}背包问题小结
第一步：翻译核心三要素（代价、价值、容量）
先分清题目里谁是花费（
cost），谁是收益（val），谁是总限制（V）。比如纪念品这题：代价是今天的价格，价值是明天的利润，容量是今天的本金。
第二步：写死外层循环，提取变量
外层永远是遍历物品种类（或者天数、阶段）。
for(inti=1;i<=n;i++){intcost=...;// 明确写出代价是什么intval=...;// 明确写出价值是什么}建议：不要在内层循环的状态转移方程里写一大堆。用明确的变量名（例如：
cost和val）替换带有复杂下标的二维数组（比如本题的：a[i+1][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);