CSP 2019 第三题纪念品题目链接题目题意数据给出能预测的天数纪念品种类持有金币。每天对金币进行买卖求买卖后的金币最大值如何赚得更多知识点考动态规划思路按照题意能够知道赚得最多就是保证每天都赚最多就行。最简单想法就是第二天根据某纪念品的涨幅先买涨价最多的如果持有金币还有就继续买涨价次之的币种可以结构体排序然后根据剩余一次购买。这个方法真的很贪心每次都是买“性价比”最高的但是这个方法只能局部最优举个例子我有100元某个纪念品初值25元能赚6元另一个纪念品初值20元能赚5元。按照贪心算法定是要买赚8元的只赚6424元但是如果我买初值20元的就是5*525。所以这个时候看出来明显不是最优的。所以贪心算法求最值问题时不一定能办到全部最优个别样例倒是能过。涉及最值问题存在重叠子问题时优先想到用动态规划来做。物品可选一个或者多个是完全背包板子用得上唯一加了点难度就是同一天交易的物品是多个dp[j]表示第i天金币为j时的交易所得最大值因此只需要再完全背包基础上再遍历当天的所有物品金币为j时若“再买一次该纪念品”判断是买当前纪念品是否能“赚钱”状态转移方程-明确状态每天根据买卖金币会变化根据金币大小选择买不买当天纪念品-明确选择每天选择买卖时通常是判断买某个纪念品后的利润买之前持有金币的利润是否变大每次买一个纪念品这样遍历时就能判断是买纪念品A还是买纪念品B划算而不是以为的买涨幅最大的纪念品-明确数组或者dp函数定义所以置数组dp[i]一维数组放每天金币为i时能求的利润最值就行数据约束数据相对比较小注意数组范围100就行代码注意如果是边输入数据边处理是否购买那么i一定是从1开始并且要处理第0排的数据(第一天不可能会产生利润)否则一开始dp数据就会不准确如果输入完数据遍历时i就从第二排开始就行最后每行处理完要初始化我们的dp数组参考代码#includebits/stdc.h#defineMAX_N105usingnamespacestd;inta[MAX_N][MAX_N];//动态规划思想处理intdp[10005]{0};//结果只和金币m有关,dp[i]表示持有i个金币时利润最大值intmain(){intt,n,m;cintnm;memset(a,0x3f,sizeof(a));//也可以不初始化但是后面第一行不赚钱需要特判for(inti1;it;i){for(intj1;jn;j){cina[i][j];intk0a[i][j]-a[i-1][j];//差值0有利润才做记录if(k00){for(intpa[i-1][j];pm;p){//至少要a[i-1][j]个金币才能购买记录最低需要的金币到金币m区间买该金币后的收益dp[p]max(dp[p],dp[p-a[i-1][j]]k0);//买之前的利润(当前金币下的最有买法)和买之后的利润做对比}}}mdp[m];// 初始化结构体memset(dp,0,sizeof(dp));//每一行遍历完后就重置数组}coutm;return0;}贪心算法试了一下果然是样例很多不会过仅35%不能AC贪心算法如下#includebits/stdc.h#defineMAX_N105usingnamespacestd;inta[MAX_N][MAX_N];//定义一个结构体数组储存金币差值和上一天的金币价格 金币遍历从差值最高的开始structstu{intk;//记录差值intm0;}s[MAX_N];intcmp(stu st1,stu st2){returnst1.kst2.k;}intmain(){intt,n,m,mm1e4;//mm存储一行的最小值cintnm;// 处理第0排数据memset(a,1e4,sizeof(a));for(inti1;it;i){for(intj1;jn;j){cina[i][j];if(j-10){intk0a[i][j]-a[i-1][j];//差值0才做记录if(k00){s[j].kk0;//差值s[j].m0a[i-1][j];//上一个数据的值if(a[i-1][j]mm)mma[i-1][j];}}}sort(s1,sn,cmp);intnum0,earn0;//赚到的最多的金币可能还能买到的intbeleftm,p1;while(beleftmmpn){if(belefts[p].m0s[p].k0){numbeleft/s[p].m0;earnnum*s[p].k;beleft-num*s[p].m0;}p;}mearn;mm1e4;//初始化;// 初始化结构体memset(s,0,sizeof(s));}coutm;return0;}