UVa 12563 Jin Ge Jin Qu hao (0-1背包)

发表于 更新于 分类于

题目

题目描述

(如果当你看到这个标题的时候笑了，那么这个问题是为你准备的ヽ(￣▽￣)ﾉ) 如果问一个麦霸：“你在KTV里必唱的曲目有哪些？”得到的答案通常都会包含一首“神曲”：古巨基的《劲歌金曲》。为什么呢？一般来说，KTV不会在“时间到”的时候鲁莽地把正在唱的歌切掉，而是会等它放完。例如：在还有15秒时再唱一首2分钟的歌，则实际上多唱了105秒。但是融合了37首歌曲的《劲歌金曲》长达11分18秒，如果唱这首，则相当于多长了663秒！

假设你正在唱KTV，还剩t秒时间。你决定接下来只唱你最爱的n首歌（不含《劲歌金曲》）中的一些，在时间结束之前再唱一个《劲歌金曲》，使得唱的总曲目尽量多（包含《劲歌金曲》），在此前提下尽量晚的离开KTV。 输入n(n<=50)，t(t<=10的9次方)和每首歌的长度(保证不超过3分钟)，输出唱的总曲目以及时间总长度。输入保证所有n+1首曲子的总长度严格大于t。

输入输出格式

输入格式

***

输出格式

***

输入输出样例

输入样例

1
2
3
4
5
2
3 100
60 70 80
3 100
30 69 70

输出样例

1
2
Case 1: 2 758
Case 2: 3 777

题解

0-1背包

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
#include <cstring>
#include <algorithm>
int dp[10000], t[55];
int main(int argc, char **argv){
  register int T, n, cases, len, ma;
  scanf("%d", &T);
  for (cases = 1; cases <= T; ++cases) {
    scanf("%d%d", &n, &len);
    len = len > 9678 ? 9678 : len;
    --len;
    for (register int i(1); i <= n; ++i) scanf("%d", &t[i]);
    memset(dp, 0, sizeof(dp));
    ma = 0;
    for (register int i(1); i <= n; ++i) {
      for (register int j(len); j >= t[i]; --j) {
        if (dp[j - t[i]] >= 1 || j == t[i]) {
          dp[j] = std::max(dp[j],dp[j-t[i]]+1);
          ma = std::max(ma, dp[j]);
        }
      }
    }
    register int i(len);
    for (; dp[i] != ma; --i) {}
    if (!ma) printf("Case %d: %d %d\n", cases,1,678);
    else printf("Case %d: %d %d\n", cases, 1 + ma, i + 678);
  }
  return 0;
}