contents
Problem
目標從起始序列經過操作變成目標序列。
- 操作 1 : 任意替除掉一個元素。
- 操作 2 : 將元素插入到任意位置。
請問最少次數為何
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
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; 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: %dn", ++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 */
|
近期评论