alan23273850 的刷題筆記
a133: 10066 - The Twin Towers
出處：https://zerojudge.tw/ShowProblem?problemid=a133
提交：https://zerojudge.tw/Submissions?problemid=a133&account=allllllan123456
問題：給定兩個長度分別介於 $[1,100]$ 的整數陣列，請求出它們的最長共同子序列長度？
解法：就很經典可以用 DP 解決的老問題，跟 d674 一模一樣，直接把 code 拿來改即可！
1#include <bits/stdc++.h>
2using namespace std;
3
4short dp[100][100];
5int a[100], b[100];
6
7int lcs(int x, int y) {
8 if (x<0 || y<0) return 0;
9 if (dp[x][y] >= 0) return dp[x][y];
10 if (a[x] == b[y]) return dp[x][y] = lcs(x-1, y-1) + 1;
11 return dp[x][y] = max(lcs(x-1, y), lcs(x, y-1));
12}
13
14int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
15 int N1, N2, T = 0;
16 while (cin >> N1 >> N2 && (N1||N2)) { memset(dp, -1, sizeof dp);
17 for (int i=0; i<N1; i++) cin >> a[i];
18 for (int i=0; i<N2; i++) cin >> b[i];
19 cout << "Twin Towers #" << ++T << "\nNumber of Tiles : " << lcs(N1-1, N2-1) << "\n\n";
20 }
21 return 0;
22}