学步园

题目链接：http://uva.onlinejudge.org/external/125/12563.pdf

思路：DP，用01背包的思路，每次记录下每个时间的最大歌曲数，最后找答案先满足歌曲数最大，在满足时间最大

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 55;

int T, n, t, sing[N], dp[11005];

int main() {
	int cas = 0;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &t);
		for (int i = 0; i < n; i++)
			scanf("%d", &sing[i]);
		sing[n++] = 678;
		memset(dp, -1, sizeof(dp));
		dp[0] = 0;
		for (int i = 0; i < n; i++) {
			for (int j = min(t - 1, 10000); j >= 0; j--) {
				if (dp[j] != -1)
					dp[j + sing[i]] = max(dp[j + sing[i]], dp[j] + 1);
   			}
  		}
  		int ans1 = 0, ans2;
  		for (int i = 11000; i >= 0; i--) {
  			if (ans1 < dp[i]) {
  				ans1 = dp[i];
 				ans2 = i;
     		}
    	}
    	printf("Case %d: %d %d\n", ++cas, ans1, ans2);
 	}
	return 0;
}