nyoj 最长公共子序列(LCS)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<string>
 6 #include<queue>
 7 #include<algorithm>
 8 #include<map>
 9 #include<iomanip>
10 #include<climits>
11 #include<string.h>
12 #include<cmath>
13 #include<stdlib.h>
14 #include<vector>
15 #include<stack>
16 #include<set>
17 #define INF 1e7
18 #define MAXN 100010
19 #define maxn 1000010
20 #define Mod 1000007
21 #define N 1010
22 using namespace std;
23 typedef long long LL;
24 
25 int T;
26 string a, b;
27 int dp[N][N];
28 
29 void run()
30 {
31     memset(dp, 0, sizeof(dp));
32     cin >> a >> b;
33     for (int i = 0; i < a.length(); ++i)
34         for (int j = 0; j < b.length(); ++j)
35             if (a[i] == b[j])
36                 dp[i + 1][j + 1] = dp[i][j] + 1;
37             else
38                 dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
39     cout << dp[a.length()][b.length()] << endl;
40 }
41 
42 int main()
43 {
44     cin >> T;
45     while (T--)
46         run();
47     //system("pause");
48     return 0;
49 }