例9-1 UVa1025 A Spy in the Metro
每一个时刻都有3个决策：在当前车站等一下，从向左开的车上下车，从向右开的车上下车。
由于“坐在车上”这个状态不好表示，因此相应的替换为后两个状态。
由于要表示当前时刻和当前车站，因此用$dp(i, j)$表示当前在$i$时刻，$j$车站，最少的在车站的时间。这样的话整个dp的时间复杂度为$O(nT)$。
注意越界！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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, T, m1, m2;
int dp[255][55], t[55];
bool has[255][55][2];
void init(){
T = read();
t[0] = t[n] = 0;
for(int i = 1; i < n; ++i)
t[i] = read();
memset(has, 0, sizeof(has));
m1 = read();
for(int i = 0; i < m1; ++i) {
int tt = read();
for(int j = 1; j <= n; ++j){
if(tt > T) break;
has[tt][j][0] = 1,
tt += t[j];
}
}
m2 = read();
for(int i = 0; i < m2; ++i) {
int tt = read();
for(int j = n; j >= 1; --j){
if(tt > T) break;
has[tt][j][1] = 1,
tt += t[j - 1];
}
}
}
void solve(){
memset(dp, 0x3f, sizeof(dp));
dp[0][1] = 0;
for(int i = 1; i <= T; ++i)
for(int j = 1; j <= n; ++j){
int& d = dp[i][j];
d = dp[i - 1][j] + 1;
if(j > 1 && has[i][j][0] && i >= t[j - 1])
d = min(d, dp[i - t[j - 1]][j - 1]);
if(j < n && has[i][j][1] && i >= t[j])
d = min(d, dp[i - t[j]][j + 1]);
}
if(dp[T][n] > T) printf("impossible\n");
else printf("%d\n", dp[T][n]);
}
int main(){
int kase = 1;
while(n = read()){
printf("Case Number %d: ", kase++);
init();
solve();
}
return 0;
}
例9-2 UVa437 The Tower of Babylon
一个扩展性的矩阵嵌套问题？
我设计的状态是$dp(i, j, id)$表示塔的第$i$块砖为第$j$个方块，并且高的编号为$id$时塔的最高高度。这样由于每一次转移只需要枚举之前一次放上去的方块，就可以判断是否合法。
由于至多需要$2n$层，每一层的决策数都为$O(n)$，故总的时间复杂度为$O(n^2)$。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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int dp[63][33][3], n, ord[33][3];
void init(){
int x[3];
for(int i = 0; i < n; ++i){
for(int j = 0; j < 3; ++j)
x[j] = read();
sort(x, x + 3);
for(int j = 0; j < 3; ++j)
ord[i][j] = x[2 - j];
}
}
void solve(){
memset(dp, 0, sizeof(dp));
for(int i = 0; i < n; ++i)
for(int j = 0; j < 3; ++j)
dp[1][i][j] = ord[i][j];
int ans = 0;
for(int i = 2; ; ++i){
int flag = 0;
for(int j = 0; j < n; ++j)
for(int k = 0; k < 3; ++k){
int &d = dp[i][j][k];
int a, b;
if(k == 0) a = ord[j][1], b = ord[j][2];
if(k == 1) a = ord[j][0], b = ord[j][2];
if(k == 2) a = ord[j][0], b = ord[j][1];
for(int jj = 0; jj < n; ++jj)
for(int kk = 0; kk < 3; ++kk){
if(!dp[i - 1][jj][kk]) continue;
int aa, bb;
if(kk == 0) aa = ord[jj][1], bb = ord[jj][2];
if(kk == 1) aa = ord[jj][0], bb = ord[jj][2];
if(kk == 2) aa = ord[jj][0], bb = ord[jj][1];
if(aa > a && bb > b)
d = max(d, dp[i - 1][jj][kk] + ord[j][k]),
ans = max(ans, d),
flag = 1;
}
}
if(!flag) break;
}
printf("%d\n", ans);
}
int main(){
int kase = 1;
while(n = read()){
printf("Case %d: maximum height = ", kase++);
init();
solve();
}
return 0;
}
例9-5 UVa12563 Jin Ge Jin Qu hao
先对前$t-1$秒跑一个背包，然后再检查一下最多的方案和对应的时间，并且加上劲歌金曲即可。
原因是因为劲歌金曲唱了一定比不唱好，所以$t$要减掉一。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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, t, len[55], dp[10005];
void init(){
n = read(), t = read();
for(int i = 0; i < n; ++i)
len[i] = read();
}
void solve(){
memset(dp, -1, sizeof(dp));
dp[0] = 0;
t--;
for(int i = 0; i < n; ++i)
for(int j = t; j >= len[i]; --j)
if(dp[j - len[i]] >= 0)
dp[j] = max(dp[j], dp[j - len[i]] + 1);
int ans = -1, maxi;
for(int i = t; i >= 0; --i)
if(dp[i] > ans)
ans = dp[i], maxi = i;
printf("%d %d\n", ans + 1, maxi + 678);
}
int main(){
int T = read();
for(int i = 1; i <= T; ++i){
printf("Case %d: ", i);
init();
solve();
}
return 0;
}