本文主要是介绍uva12563 Jin Ge Jin Qu，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxx = 180 * 55;
int t[55];//题目所给的歌的每个时长struct Node{int num, time;//歌的数量和时长
}dp[maxx];int main()
{int l;int n, len, sum = 0;//len控制时长,sum为了判断所给的歌的总时长int max_time;//为了判断所给len时长与sum大小int cnt = 1;scanf("%d", &l);while(l--){scanf("%d%d", &n, &len);memset(dp, 0, sizeof(dp));memset(t, 0, sizeof(t));for(int i = 1; i <= n; i++) {scanf("%d", &t[i]); sum += t[i];}max_time = min(sum, len - 1);//最多也是时长限制-1for(int i = 1; i <= n; i++){for(int j = max_time; j >= t[i]; j--){Node s; //这里用Node 其实就是降维度的一个写法，从max_time to t[i]这种写法可以降维度其实和最简单的01背包相同s.num = dp[j-t[i]].num + 1;//这里一定记得搞清楚是”前“i件物品（歌）的总和，自己不懂可以推一下s.time = dp[j-t[i]].time + t[i];if(dp[j].num < s.num){//这个题歌的数量优先 dp[j]表示当前容量下的个数，s.num表示前i首歌的总个数dp[j].num = s.num;dp[j].time = s.time;}else if(dp[j].num == s.num && dp[j].time < s.time){//相同个数的歌需要保证最长时间dp[j].num = s.num;dp[j].time = s.time;}}}cout <<"Case " << cnt++ << ": " << dp[max_time].num + 1 << " " << dp[max_time].time + 678 << endl << max_time;//这里+1的原意是结构体初始化为0//其实博主刚开始很诧异为什m最终最多的个数会更新到max_time上，这是由于第一个if，自己不懂过程的一定自己在纸上推一下，懂过程以后代码就显得简单了}return 0;
}
这篇关于uva12563 Jin Ge Jin Qu的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
