首页 > 代码库 > UVA - 12563 Jin Ge Jin Qu hao （01背包）
UVA - 12563 Jin Ge Jin Qu hao （01背包）
首先这题的题意要先读懂，而不是一看到01背包的问题就开始敲。
题目大意：
如果问一个麦霸：“你在KTV里面必唱的歌曲有那些”，得到的答案可能会包含古巨基的《劲歌金曲》，一般来说KTV不会在时间到的时候把正在唱的歌给切掉，而是会等它放完，例如还有15秒时再唱一首2分钟的歌，则实际上多唱了105秒。但是唱“神曲”《劲歌金曲》则相当于多唱了663秒。
现在要求你在唱的歌曲的曲数尽量多的情况下，唱的时间尽量长。
思路：
题目大意：
如果问一个麦霸：“你在KTV里面必唱的歌曲有那些”，得到的答案可能会包含古巨基的《劲歌金曲》，一般来说KTV不会在时间到的时候把正在唱的歌给切掉，而是会等它放完，例如还有15秒时再唱一首2分钟的歌，则实际上多唱了105秒。但是唱“神曲”《劲歌金曲》则相当于多唱了663秒。
现在要求你在唱的歌曲的曲数尽量多的情况下，唱的时间尽量长。
思路：
01背包的思路，每次记录下每个时间的最大歌曲数，最后找答案先满足歌曲数最大，再满足时间最大。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55;
const int MAX_TIME = 100005;
int song[N],dp[MAX_TIME];
int n,t;
int main() {
int T,cas = 1;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&t);
for(int i = 0; i < n; i++) {
scanf("%d",&song[i]);
}
memset(dp,-1,sizeof(dp));
dp[0] = 0;
for(int i = 0; i < n; i++) {
for(int j = min(t-1,MAX_TIME) ; j >= song[i]; j--) {
if(dp[j - song[i]] != -1)
dp[j] = max(dp[j],dp[j-song[i]]+1);
}
}
int maxn = 0, time;
for(int i = MAX_TIME - 1; i >= 0; i--) {
if(maxn < dp[i]+1) {
maxn = dp[i]+1;
time = i;
}
}
printf("Case %d: %d %d\n",cas++,maxn,time + 678);
}
return 0;
}UVA - 12563 Jin Ge Jin Qu hao （01背包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。