题目大意：
你在ktv唱歌，有一个时限，但是在时限到时，若一首歌没唱完可以继续唱，已知有n首歌可以唱，已知他们的时长每个都不超过3分钟
不能重复唱一首歌。还有一首678秒的歌，歌之间可以无缝衔接
思路：
典型的背包问题
求这n首歌能达到不超过t-1的时间
t-1是因为要留出1秒来开始那个巨长的歌
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 #include<vector> 7 #include<queue> 8 #include<algorithm> 9 #define inf 2147483611 10 #define ll long long 11 #define MAXN 101010 12 #define MOD 905229641 13 using namespace std; 14 inline int read() 15 { 16 int x=0,f=1; 17 char ch;ch=getchar(); 18 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} 19 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 20 return x*f; 21 } 22 int n,k,a[55],t; 23 int T,dp[MAXN],ans,res; 24 int main() 25 { 26 T=read(); 27 for(int y=1;y<=T;y++){ 28 ans=res=0; 29 n=read(),t=read();t--; 30 for(int i=1;i<=n;i++) a[i]=read(); 31 t=min(t,100000); 32 memset(dp,0xff,sizeof(dp));dp[0]=0; 33 for(int i=1;i<=n;i++) 34 for(int j=t;j>=0;j--) if(dp[j]>=0) dp[j+a[i]]=max(dp[j+a[i]],dp[j]+1); 35 for(int i=1;i<=t;i++) if(ans<=dp[i]) ans=dp[i],res=i; 36 printf("Case %d: %d %d ",y,ans+1,res+678);} 37 }