题目概要
题目传送门.
已知T天内N种物品的价格，以及开始时拥有M枚金币，每天可以当日价格或卖出物品，问T天后最多可以拥有多少枚金币？
数据分析
考场骗分
很明显，T=1时，初始金币数即为最终金币数，相信大家都会，此处就不单独给代码了。
当N=1时，这个问题变成了一个很基础很基础的贪心
以下为正解
此时我们注意到有15%的测试点是T=2，我们分析了这个情况之后，就会发现这其实是一个完全背包的模版：背包容量为手里的钱数，物品价值为差价，物品体积为物品价格
当T大于等于2时，我们就需要对每一天进行一次完全背包，将结果相加即为最终的答案
以下为完整代码
#include<bits/stdc++.h>usingnamespacestd;intn,m,t;intp[105][105];// 全局dp，避免栈溢出intdp[100005];voidcheck1(){intans=m;for(inti=0;i<t-1;i++)// 最多到t-2天{if(p[i+1][0]>p[i][0]){intcnt=ans/p[i][0];ans=ans%p[i][0]+cnt*p[i+1][0];}}cout<<ans;}voidcheck2(){memset(dp,0,sizeof(dp));for(inti=0;i<n;i++){intcost=p[0][i];intv=p[1][i]-cost;if(v<=0)continue;for(intj=cost;j<=m;j++){dp[j]=max(dp[j],dp[j-cost]+v);}}cout<<m+dp[m];}voidcheck3(){for(intday=0;day<t-1;day++)//对每一天进行遍历{memset(dp,0,sizeof(dp));for(inti=0;i<n;i++)//完全背包{intcost=p[day][i];intv=p[day+1][i]-cost;if(v<=0)continue;for(intj=cost;j<=m;j++){dp[j]=max(dp[j],dp[j-cost]+v);}}m+=dp[m];}cout<<m;}intmain(){cin>>t>>n>>m;for(inti=0;i<t;i++){for(intj=0;j<n;j++){cin>>p[i][j];}}if(t==1)//特殊情况1{cout<<m;return0;}if(n==1)//特殊情况2：贪心{check1();return0;}if(t==2)//特殊情况3：背包{check2();return0;}check3();//正解return0;}本人第一篇题解，如有错误，请各位大佬支出
