首页 > 代码库 > UVa 12563 (01背包) Jin Ge Jin Qu hao
UVa 12563 (01背包) Jin Ge Jin Qu hao
如此水的01背包，居然让我WA了七次。
开始理解错题意了，弄反了主次关系。总曲目最多是大前提，其次才是歌曲总时间最长。
题意：
在KTV房间里还剩t秒的时间，可以从n首喜爱的歌里面选出若干首(每首歌只能唱一次且如果唱就必须唱完)，然后剩下至少1秒的时间来唱那首长678秒的歌曲。
总曲目最多的前提下，尽量使歌曲总时间最长。
分析：
所给时间为t，在t-1秒内进行01背包，num[i]来记录剩余时间为 i 时能长的最多曲目，如果曲目相同还要记录最长时间。
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 10000; 8 int a[55], dp[maxn], num[maxn]; 9 10 int main(void)11 {12 #ifdef LOCAL13 freopen("12563in.txt", "r", stdin);14 #endif15 16 int T;17 scanf("%d", &T);18 for(int kase = 1; kase <= T; ++kase)19 {20 int n, t;21 scanf("%d%d", &n, &t);22 t--;23 for(int i = 0; i < n; ++i)24 {25 scanf("%d", &a[i]);26 if(a[i] > 180) a[i] = 180;27 }28 memset(dp, 0, sizeof(dp));29 memset(num, 0, sizeof(num));30 for(int i = 0; i < n; ++i)31 for(int j = t; j >= a[i]; --j)32 {33 if(num[j] < num[j-a[i]] + 1)34 {35 num[j] = num[j-a[i]] + 1;36 dp[j] = dp[j-a[i]] + a[i];37 }38 else if(num[j] == num[j-a[i]] + 1)39 {40 dp[j] = max(dp[j], dp[j-a[i]] + a[i]);41 }42 }43 printf("Case %d: %d %d\n", kase, num[t]+1, dp[t]+678);44 }45 46 return 0;47 }
UVa 12563 (01背包) Jin Ge Jin Qu hao
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。