题意：
给出t组数据，每组数据再给出num和time，代表下面共有三首歌曲和总共演唱时间，要求求出最长演唱时间和最多歌曲数量，输出时长，若是还有剩余时间，则可以演唱长为678s的歌曲
再给出一组数据
1
3 100
100 100 100 输出：678
为什么我一开始会想到用暴力来写。。。我只想到了一点是对的，就是时间刚开始处理的时候-1。其他没了。。
注意：这里对于dp数组的处理需要注意一下
dp[i]记录的是歌曲数目，里面的i记录的是时长
1 #include<stdio.h> 2 #include<string.h> 3 #include<iostream> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 #define inf 0x3f3f3f3f 8 typedef long long ll; 9 10 int a[5500]; 11 int dp[5500]; 12 int main() 13 { 14 int t=1; 15 int tt; 16 int num,time; 17 scanf("%d",&tt); 18 while(tt--) 19 { 20 scanf("%d %d",&num,&time); 21 for(int i=1; i<=num; i++) 22 scanf("%d",&a[i]); 23 time--; 24 memset(dp,0,sizeof(dp)); 25 dp[0]=1; 26 for(int i=1; i<=num; i++) 27 { 28 for(int j=time; j>=a[i]; j--) 29 dp[j]=max(dp[j],dp[j-a[i]]+1); 30 } 31 32 int kk=0; 33 int maxx=0; 34 for(int i=0; i<=time; i++) 35 { 36 if(dp[i]>=maxx) 37 { 38 maxx=dp[i]; 39 kk=i; 40 //printf("%d ",i); 41 } 42 } 43 // printf("Case %d: %d %d\n",t++,kk,maxx+678); 44 printf("Case %d: %d %d\n",t++,maxx,kk+678); 45 } 46 return 0; 47 }
UVA-12563-Jin Ge Jin Qu hao-01背包
原文：https://www.cnblogs.com/OFSHK/p/11393226.html