alan23273850 的刷題筆記
a676: 00111 - History Grading
出處：https://zerojudge.tw/ShowProblem?problemid=a676
提交：https://zerojudge.tw/Submissions?problemid=a676&account=allllllan123456
問題：給定多個長度皆為 $n\in[2,20]$ 而且都包含 1 ~ n 的正整數陣列，第 i 個數字 m 代表序列的第 m 個數字為 i，舉例來說，3 1 2 4 9 5 10 6 8 7 轉換後的結果為 2 3 1 4 6 8 10 9 5 7，請問其他陣列分別與第一個陣列在轉換過後的最長共同子序列長度？
解法：就很經典可以用 DP 解決的老問題，可以直接拿 a133 的 code 來改。
1#include <bits/stdc++.h>
2using namespace std;
3
4char dp[20][20], a[20], b[20];
5
6int lcs(int x, int y) {
7 if (x<0 || y<0) return 0;
8 if (dp[x][y] >= 0) return dp[x][y];
9 if (a[x] == b[y]) return dp[x][y] = lcs(x-1, y-1) + 1;
10 return dp[x][y] = max(lcs(x-1, y), lcs(x, y-1));
11}
12
13int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
14 int t, n; cin >> n;
15 for (int i=0; i<n; i++) cin >> t, a[t-1] = i;
16 while (cin >> t) { memset(dp, -1, sizeof dp); b[t-1] = 0;
17 for (int i=1; i<n; i++) cin >> t, b[t-1] = i;
18 cout << lcs(n-1, n-1) << '\n';
19 }
20 return 0;
21}