紫书习题 第九章

发表于 | 分类于 |
字数统计: 1,275 字

我自己做的紫书第九章部分习题的整合。

例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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
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;
}

Powered By Valine
v1.5.2