P5662 [CSP-J 2019] 纪念品题目描述小伟突然获得一种超能力他知道未来TTT天NNN种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量以及卖出一个该纪念品换回的金币数量。每天小伟可以进行以下两种交易无限次任选一个纪念品若手上有足够金币以当日价格购买该纪念品卖出持有的任意一个纪念品以当日价格换回金币。每天卖出纪念品换回的金币可以立即用于购买纪念品当日购买的纪念品也可以当日卖出换回金币。当然一直持有纪念品也是可以的。TTT天之后小伟的超能力消失。因此他一定会在第TTT天卖出所有纪念品换回金币。小伟现在有MMM枚金币他想要在超能力消失后拥有尽可能多的金币。输入格式第一行包含三个正整数T,N,MT, N, MT,N,M相邻两数之间以一个空格分开分别代表未来天数TTT纪念品数量NNN小伟现在拥有的金币数量MMM。接下来TTT行每行包含NNN个正整数相邻两数之间以一个空格分隔。第iii行的NNN个正整数分别为Pi,1,Pi,2,…,Pi,NP_{i,1},P_{i,2},\dots,P_{i,N}Pi,1​,Pi,2​,…,Pi,N​其中Pi,jP_{i,j}Pi,j​表示第iii天第jjj种纪念品的价格。输出格式输出仅一行包含一个正整数表示小伟在超能力消失后最多能拥有的金币数量。输入输出样例 #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 说明最佳策略是第二天花光所有100100100枚金币买入555个纪念品111第三天卖出555个纪念品111获得金币125125125枚第四天买入666个纪念品111剩余555枚金币第六天必须卖出所有纪念品换回300300300枚金币第四天剩余555枚金币共305305305枚金币。超能力消失后小伟最多拥有305305305枚金币。样例 2 说明最佳策略是第一天花光所有金币买入101010个纪念品111第二天卖出全部纪念品111得到150150150枚金币并买入888个纪念品222和111个纪念品333剩余111枚金币第三天必须卖出所有纪念品换回216216216枚金币第二天剩余111枚金币共217217217枚金币。超能力消失后小伟最多拥有217217217枚金币。数据规模与约定对于10%10\%10%的数据T1T 1T1。对于30%30\%30%的数据T≤4,N≤4,M≤100T \leq 4, N \leq 4, M \leq 100T≤4,N≤4,M≤100所有价格10≤Pi,j≤10010 \leq P_{i,j} \leq 10010≤Pi,j​≤100。另有15%15\%15%的数据T≤100,N1T \leq 100, N 1T≤100,N1。另有15%15\%15%的数据T2,N≤100T 2, N \leq 100T2,N≤100。对于100%100\%100%的数据T≤100,N≤100,M≤103T \leq 100, N \leq 100, M \leq 10^3T≤100,N≤100,M≤103所有价格1≤Pi,j≤1041 \leq P_{i,j} \leq 10^41≤Pi,j​≤104数据保证任意时刻小伟手上的金币数不可能超过10410^4104。C实现#includeiostream#includecstring#includecstdiousingnamespacestd;constintMAXN105;intdp[10005],price[MAXN][MAXN];intmain(){intt,n,m,ans;scanf(%d%d%d,t,n,m);for(inti1;it;i){for(intj1;jn;j){scanf(%d,price[i][j]);}}ansm;for(inti1;it;i){memset(dp,~0x3f,sizeof(dp));dp[ans]ans;for(intj1;jn;j){for(intkans;kprice[i][j];--k){dp[k-price[i][j]]max(dp[k-price[i][j]],dp[k]price[i1][j]-price[i][j]);}}intma0;for(intj0;jans;j){mamax(ma,dp[j]);}ansma;}coutansendl;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容