打卡信奥刷题（2925）用C++实现信奥题P5627 P5662 [CSP-J 2019] 纪念品

P5662 [CSP-J 2019] 纪念品

题目描述

小伟突然获得一种超能力，他知道未来TTT天NNN种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。

每天，小伟可以进行以下两种交易无限次：

1. 任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；
2. 卖出持有的任意一个纪念品，以当日价格换回金币。

每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。

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

输入 #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 说明

最佳策略是：

第二天花光所有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%的数据，T=1T = 1T=1。

对于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,N=1T \leq 100, N = 1T≤100,N=1。

另有15%15\%15%的数据，T=2,N≤100T = 2, N \leq 100T=2,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++实现

#include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;constintMAXN=105;intdp[10005],price[MAXN][MAXN];intmain(){intt,n,m,ans;scanf("%d%d%d",&t,&n,&m);for(inti=1;i<=t;++i){for(intj=1;j<=n;++j){scanf("%d",&price[i][j]);}}ans=m;for(inti=1;i<t;++i){memset(dp,~0x3f,sizeof(dp));dp[ans]=ans;for(intj=1;j<=n;++j){for(intk=ans;k>=price[i][j];--k){dp[k-price[i][j]]=max(dp[k-price[i][j]],dp[k]+price[i+1][j]-price[i][j]);}}intma=0;for(intj=0;j<=ans;++j){ma=max(ma,dp[j]);}ans=ma;}cout<<ans<<endl;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容