简答题
偏难
#22106
纪念品
纪念品


答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include<iostream>
#include<cstring>
using namespace std;
int T,N,M;
int dp[10001];
int price[101][10001];
int main(){
cin>>T>>N>>M;
for(int i=1;i<=T;i++){
for(int j=1;j<=N;j++){
cin>>price[i][j];
}
}
int maxn=0;
for(int i=2;i<=T;i++){
maxn=0;
memset(dp,0,sizeof(dp));
for(int j=1;j<=N;j++){
for(int k=price[i-1][j];k<=M;k++){
dp[k]=max(dp[k],dp[k-price[i-1][j]]+price[i][j]-price[i-1][j]);
maxn=max(maxn,dp[k]);
}
}
M+=maxn;
}
cout <<M<< endl;
return 0;
}</pre><p><br/></p>
解析
如果只有1天的话,买了再卖,总共剩下M个金币。
T天N种纪念币,根据题目设定范围,100以内,可以用二维表格推导。
时间不可逆,只能1~N。
每天买哪些纪念品呢?根据测试样例分析,纪念品任意多,没有个数限制。根据金币的上限,可以推到出这个就是完全背包。大家可以套一下完全背包的算法。每天需要做一次完全背包处理,当天不想卖出金币,相当于卖出金币再买入金币。