UVA 12563 Jin Ge Jin Qu hao(DP)

UVA 12563 Jin Ge Jin Qu hao(DP)

思路：DP，用01背包的思路，每次記錄下每個時間的最大歌曲數，最後找答案先滿足歌曲數最大，在滿足時間最大

#include 
#include 
#include 
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
, ++cas, ans1, ans2);
 	}
	return 0;
}