解題區/解題區 - UVa

UVa 1579 - Matryoshka

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

俄羅斯套娃遊戲，每一次只能將相鄰的兩個套娃合併。合併時，打開套娃的次數相當於操作成本，請問至少要打開的次數為何，使得最後的數個套娃可以收成連續大小 1 ~ n。

一開始給定每個套娃內部都沒有別的套娃。

從第二組測資中，可以看出必須整理成 [1 2 3][1 2 3 4] 兩組完整的套娃。要把 [2][4] 合併成 [2 4] 要打開大小為 4 的套娃，並且把大小為 2 的套娃裝進去。同理，[1][3] 合併成 [1 3] 也需要打開一次。最後合併 [2 4][1 3] 成 [1 2 3 4] 其中必須將 4 打開 (看到 2)，再把 2 打開，把 3 打開，接著把 1 裝進 2，把 2 裝進 3，最後裝進 4 中。

此時已經花費成本 5 次 (打開次數)，而要把 [1][2][3] 合併成 [1 2 3] 需要打開 2、打開 3 才能完成。共計成本 7 次。

Sample Input

1
2
3
4
7
1 2 1 2 4 3 3
7
1 2 3 2 4 1 3

Sample Output

1
2
impossible
7

Solution

類似矩陣鏈乘積 DP，但是這一題必須使用兩次 DP。

  1. 第一次計算 dp[l, r] 找到序列 [l, r] 之間合併成一個套娃的花費。－O(n^3)
  2. 之後檢查 A[l, r] 之間是否是一個 complete set，也就是一個完整的套娃 (連續大小)。－O(n^3) 這裡應該還可以更快，不過步驟 1 應該很慢，所以沒有必要。
  3. 最後，組合數個連續區段套娃，進行區間合併的操作。－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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 512
int A[MAXN];
int dp[MAXN][MAXN] = {}, complete[MAXN][MAXN];
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        
        for (int i = 1; i < n; i++) { // build cost table.
            for (int j = 0; i + j < n; j++) {
                int l = j, r = i + j;
                int &val = dp[l][r];
                val = 0x3f3f3f3f;
                for (int k = l; k < r; k++) {
                    int open = 0; // [l, r] = L[l, k] + R[k+1, r]
                    int minL = 0x3f3f3f3f, minR = 0x3f3f3f3f;
                    for (int p = l; p <= k; p++)
                        minL = min(minL, A[p]);
                    for (int p = k+1; p <= r; p++)
                        minR = min(minR, A[p]);
                    for (int p = l; p <= k; p++)
                        open += A[p] > minR;
                    for (int p = k+1; p <= r; p++)
                        open += A[p] > minL;
//					printf("[%d %d %d %d] %d %d\n", l, k, k+1, r, dp[l][k] + dp[k+1][r]+ open, open);
                    val = min(val, dp[l][k] + dp[k + 1][r] + open); 
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; i + j < n; j++) {
                int l = j, r = i + j, m = i + 1; // [l, r] need 1, 2, 3, ..., m
                int used[MAXN] = {}, ok = 1;
                for (int k = l; k <= r && ok; k++) {
                    if (A[k] > m) {
                        ok = 0;
                        break;
                    }
                    used[A[k]]++;
                    if (used[A[k]] > 1)	ok = 0;
                }
                complete[l][r] = ok;
            }
        }
        
        int dp2[MAXN];
        for (int i = 0; i <= n; i++)
            dp2[i] = 0x3f3f3f3f;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (complete[i][j]) {
                    int comb = dp[i][j];
                    if (i)	comb += dp2[i-1];
                    dp2[j] = min(dp2[j], comb);
                }
            }
        }
        if (dp2[n - 1] == 0x3f3f3f3f)
            puts("impossible");
        else
            printf("%d\n", dp2[n - 1]);
    }
    return 0;
}
/*
7
1 2 1 2 4 3 3
7
1 2 3 2 4 1 3
2
1 1
2 
2 1
5
1 3 2 3 1
5
1 2 2 3 1
*/