Jin Ge Jin Qu hao
UVA12563
定义：dp[i][j]为考虑前i首歌并且总时长为j时最多能唱的歌曲数，Song[i]表示第i首歌的时长。
转移方程：
经典的01背包。
题目特殊要求在注释中说明。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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
using namespace std;
int n, T;
int Song[51], dp[51][10001];
void Input() {
cin >> n >> T;
for (int i = 1; i <= n; ++i) {
cin >> Song[i];
}
}
void DP() {
memset(dp, 0x8f, sizeof(dp));
for (int i = 0; i <= n; ++i) {
dp[i][0] = 0;
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < Song[i]; ++j) {
dp[i][j] = dp[i - 1][j];
}
for (int j = Song[i]; j <= T; ++j) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - Song[i]] + 1);
}
}
}
void Output(const int&Case) {
//枚举dp[n][j]，找出最多的歌曲数，由于要留1秒给《劲歌金曲》，所以从T-1开始枚举。
//由于要逗留最长时间，所以时间从大到小枚举，知道遇到第一个歌曲数对应的时间点
int Ans = T - 1;
for (int j = T - 1; j >= 0; j--) {
if (dp[n][j] > dp[n][Ans]) {
Ans = j;
}
}
printf("Case %d: %d %d\n", Case, dp[n][Ans] + 1, Ans + 678);
}
int main() {
int T;
cin >> T;
for (int Case = 1; Case <= T; ++Case) {
Input();
DP();
Output(Case);
}
return 0;
}
PS：可以优化成一维数组，但是嘛，怎么方便怎么来233333
