解題區/解題區 - UVa

UVa 12747 - Back to Edit Distance

contents

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

Problem

目標從起始序列經過操作變成目標序列。

  • 操作 1 : 任意替除掉一個元素。
  • 操作 2 : 將元素插入到任意位置。

請問最少次數為何

Sample Input

1
2
3
4
5
6
7
2
5
1 3 5 4 2
1 5 4 3 2
4
1 2 4 3
3 4 2 1

Sample Output

1
2
Case 1: 2
Case 2: 6

Solution

很明顯地看出，任意插入就可以直接無視，只要找有最長共同子序列即可，剩餘的元素一次替除一次插入即可。

但是最長子序列在這一題無法使用 O(n * n) 的算法，因此將其轉換成 LIS 做法，由於元素恰好不重複，可以在 O(n log n) 完成 (轉換不造成元素增加)。

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
#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
// LCS to LIS
int A[262144], B[262144];
int LIS(int A[], int n) {
    vector<int> r;
    r.push_back(A[0]);
    for (int i = 1; i < n; i++) {
        int pos = (int)(upper_bound(r.begin(), r.end(), A[i]) - r.begin());
        if (pos == r.size())
            r.push_back(A[i]);
        else
            r[pos] = A[i];
    }
    return r.size();
}
int main() {
    int testcase, cases = 0;
    int n, x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            A[x] = i;
        }
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            B[i] = A[x];
        }
        printf("Case %d: %d\n", ++cases, (n - LIS(B, n)) * 2);
    }
    return 0;
}
/*
2
5
1 3 5 4 2
1 5 4 3 2
4
1 2 4 3
3 4 2 1
*/