首页 > 代码库 > UVa 12563 劲歌金曲（0-1背包）
UVa 12563 劲歌金曲（0-1背包）
https://cn.vjudge.net/problem/UVA-12563
题意：求在给定时间内，最多能唱多少歌曲，在最多歌曲的情况下，使唱的时间最长。
思路：很明显背包容量为t-1，因为至少得留下1秒钟来放《劲歌金曲》。题目要求的首先唱的歌要多，其次才是要时间长。
这里需要用到一个技巧：对决策进行一定的限定！在计算某个时间最多唱的歌曲时，必须是该时间内恰好唱完这些歌，时间多了不行。
所以在下面的代码中，首先将d数组都声明为了-1，如果不是在该时间内正好唱完歌，那么d[j - a[i]] + 1就是0。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 6 const int maxn = 5000+5; 7 int a[maxn], d[maxn], t, n; 8 9 int main()10 {11 //freopen("D:\\txt.txt", "r", stdin);12 int cas,kase=0;13 cin >> cas;14 while (cas--)15 {16 memset(d, -1, sizeof(d));17 d[0] = 0;18 cin >> n >> t;19 for (int i = 0; i < n; i++)20 cin >> a[i];21 for (int i = 0; i < n; i++)22 {23 for (int j = t - 1; j >= a[i]; j--)24 d[j] = max(d[j], d[j - a[i]] + 1);25 }26 int cnt = 0, sum;27 for (int i = 0; i < t; i++)28 {29 if (d[i] >= cnt)30 {31 cnt = d[i];32 sum = i;33 }34 }35 printf("Case %d: %d %d\n", ++kase, cnt+1, sum + 678);36 }37 return 0;38 }
UVa 12563 劲歌金曲（0-1背包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。