题目大意就是在KTV唱歌，剩下时间t秒，给定歌n首，选择尽可能多的歌曲能在规定时间内唱，但是要尽可能的晚离开KTV，所以至少要留1秒来点“劲歌金曲”，那么01背包问题就出来了，t-1秒内，选择尽可能多的歌曲，并且曲目数相同情况，尽可能时间长一点。
设 dp1[ i ] 是 i 秒内最多能唱的曲目数 状态转移方程 dp1[ i ] = max(dp1[ i ] , dp1[ i- v ] + 1);
设 dp2[ i ] 是 i 秒内唱的最多时长 状态转移方程 dp2[ i ] = max(dp2[ i ] , dp2[ i -v ] + v);
题目中给出的剩余时间 t 的范围是小于10^9 数据范围这么大，一开数组就犯愁。
但是题目歌曲数 n 的范围是小于 50 并且每首歌最长不超过3min 劲歌金曲的长度是678秒，所以最大的时间长度是50*3*60+678 是9678 这里直接设置为10000了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10000
using namespace std;int dp1[N],dp2[N];
int time[51],cnt;int T,n,t;
int main(){scanf("%d",&T);cnt = 1;while(T--){scanf("%d%d",&n,&t);t--; //至少留1s给劲歌金曲 memset(dp1,0,sizeof(dp1));memset(dp2,0,sizeof(dp2));for(int i=0 ;i<n ;i++){scanf("%d",&time[i]);}for(int i=0 ;i<n ;i++){for(int j=t ;j>=0 ;j--){if(j>=time[i]){if((dp1[j-time[i]]+1)>dp1[j]){dp1[j] = dp1[j-time[i]]+1; //歌曲数 dp2[j] = dp2[j-time[i]]+time[i]; //歌曲总时长 }if((dp1[j-time[i]]+1)==dp1[j]){ if(dp2[j]<dp2[j-time[i]]+time[i]){ //选择歌曲时长更大的 dp2[j] = dp2[j-time[i]]+time[i];}}}}}printf("Case %d:",cnt++);printf(" %d ",dp1[t]+1);printf("%d\n",dp2[t]+678);}return 0;
}