UVA 12563 Jin Ge Jin Qu hao(DP)

本文主要是介绍UVA 12563 Jin Ge Jin Qu hao(DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：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;
}

这篇关于UVA 12563 Jin Ge Jin Qu hao(DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---