?
?
思路：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; }
?