Codeforces 10 D. LCIS
dp[i][j] 為 a[1…i], b[1…j] 結尾為 b[j] 的 LCIS 的長度。
$$dp_{i, j} := \begin{cases} \max_{p < j, b_{p} < b_{j}} dp_{i - 1, p} + 1 &, a_{i} = b_{j} \\ dp_{i - 1, j} &, \text{otherwise}. \end{cases}$$
複雜度：O(nm)，n, m 為兩序列長度。
1#pragma GCC optimization ("O3")
2#include<bits/stdc++.h>
3using namespace std;
4int main() {
5 ios::sync_with_stdio(0), cin.tie(0);
6 // INPUT
7 int L[2];
8 vector<int> v[2];
9 for (int i = 0; i < 2; i++) {
10 cin >> L[i];
11 v[i].resize(L[i] + 1);
12 for (int j = 1; j <= L[i]; j++)
13 cin >> v[i][j];
14 }
15 // LCIS
16 vector<vector<int> > dp(L[0] + 1, vector<int>(L[1] + 1));
17 vector<vector<int> > par(L[0] + 1, vector<int>(L[1] + 1));
18 for (int i = 1; i <= L[0]; i++) {
19 int p = 0;
20 for (int j = 1; j <= L[1]; j++) {
21 if (v[0][i] == v[1][j]) {
22 dp[i][j] = dp[i - 1][p] + 1;
23 par[i][j] = p;
24 } else {
25 dp[i][j] = dp[i - 1][j];
26 par[i][j] = j;
27 if (v[0][i] > v[1][j] &&
28 dp[i - 1][j] > dp[i - 1][p])
29 p = j;
30 }
31 }
32 }
33 // BACKTRACKING
34 int p = 0;
35 for (int j = 1; j <= L[1]; j++)
36 if (dp[L[0]][p] < dp[L[0]][j])
37 p = j;
38 vector<int> ans;
39 for (int i = L[0]; i > 0; i--) {
40 if (v[0][i] == v[1][p] && p != par[i][p])
41 ans.push_back(v[0][i]);
42 p = par[i][p];
43 }
44 cout << ans.size() << "\n";
45 for (int i = ans.size() - 1; i >= 0; i--)
46 cout << ans[i] << " \n"[!i];
47 return 0;
48}