题意:
) ? 最终输出num+1 和 time+678 即可.
注意: 你需要优先让歌曲数目最大的情况下,再去选择总时长最长的.
//0 KB 39 ms#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int dp[21000][2]; // 背包内容有两个，，唱的歌曲数优先，唱的时间长其次//容量最大是50*180+678，所以设成21000int main(){int _;int cnt=0;scanf("%d",&_);while(_–){memset(dp,0,sizeof(dp));int n,t;scanf("%d%d",&n,&t);for(int i=1;i<=n;i++){int v;scanf("%d",&v); //现学现用，0，1背包正向循环边输入边处理即可for(int j=t-1;j>=0;j–){if(j>=v) {if(dp[j][0]<dp[j-v][0]+1){dp[j][0]=dp[j-v][0]+1;dp[j][1]=dp[j-v][1]+v;}if(dp[j][0]==dp[j-v][0]+1){ //当唱的歌曲数一样时就去松弛唱的时间长度if(dp[j][1]<dp[j-v][1]+v)dp[j][1]=dp[j-v][1]+v;}}}}printf("Case %d: %d %d\n",++cnt,dp[t-1][0]+1,dp[t-1][1]+678);}return 0;}
把你的脸迎向阳光，那就不会有阴影
