由于此题是CSP-J考场上的一道题我们不妨先假设自己是一名菜鸟考生用一些比较新鲜的角度去做题。正文考试时会先干嘛呢那一定是去看数据范围。CSP比GESP好的点就在于它不会让你输得太难看总有几分是你水得到的。显然这里有10%的数据是很轻松就能做对的就是当T1即小伟的神力有但完全没用只能预测一天时他买纪念品却不能以更高的价格卖出因为当天的价格是不变的类似于炒股所以他最后所持有的金币数与他最开始拥有的金币数是一样的。这里就先不给代码了。相信大家都是比我厉害的大佬当然只水十分不太对得起我们辛苦的思考考虑到T100N1时有15%的数据意思是超能力持续天数变多但是只有一种商品所以操作就是如果明天价格更贵就用今天的钱买尽量多的纪念品第二天再卖掉所以第二天后手里有的金币数就该是今天能买到的*明天价格今天余数对应的代码如下intansm;for(inti0;it;i){if(p[i1][0]p[i][0]){intcntans/p[i][0];ansans%p[i][0]cnt*p[i1][0];}}coutans;进一步地我们还能看到有15%的数据是T2也就是超能力持续两天刚好够做一次交易。这时我们先来捋一捋思路小伟手中金币数一定也就是只能选择部分纪念品进行买卖每种纪念品可以购买无数次钱够最后使得第二天卖出时利益最大不难看出这是一个简单的完全背包问题手里钱数是背包容量今天的价格对应物品体积明天价格则是物品价值然后直接套完全背包模板就可以了。如果第二天价格比今天还便宜直接continue掉实际上这里做出来后就很接近最后的AC代码了因为取的是特殊值两天我们就可以尝试把这T天分成两天一次的背包即今天和明天明天和后天…以此类推要进行T-1次不过每天都要更新手里的金币数。完整代码#includebits/stdc.husingnamespacestd;intn,m,t;intp[105][105];voidcheck1(){intansm;for(inti0;it;i){if(p[i1][0]p[i][0]){intcntans/p[i][0];ansans%p[i][0]cnt*p[i1][0];}}coutans;}voidcheck2(){intdp[1000005];memset(dp,0,sizeof(dp));for(inti0;in;i){intcostp[0][i];intvp[1][i]-cost;if(v0){continue;}for(intjcost;jm;j){dp[j]max(dp[j],dp[j-cost]v);}}coutmdp[m];}voidcheck3(){intdp[100005];for(intd0;dt-1;d){memset(dp,0,sizeof(dp));for(inti0;in;i){intcostp[d][i];intvp[d1][i]-cost;if(v0){continue;}for(intjcost;jm;j){dp[j]max(dp[j],dp[j-cost]v);}}mdp[m];}coutm;}intmain(){cintnm;for(inti0;it;i){for(intj0;jn;j){cinp[i][j];}}if(t1){coutm;return0;}if(n1){check1();return0;}if(t2){check2();return0;}//以上是前面的骗分环节只保留check3也行check3();return0;}注老师作业要求不喜勿喷
