最简单最基本的
最长公共子序列的题目。
吐槽一下为何没有给数据范围。。
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxn = 1010; 9 int dp[maxn][maxn]; 10 char s1[maxn], s2[maxn]; 11 12 int main(void) 13 { 14 #ifdef LOCAL 15 freopen("1159in.txt", "r", stdin); 16 #endif 17 18 while(cin >> s1 >> s2) 19 { 20 int len1, len2, i, j; 21 len1 = strlen(s1); 22 len2 = strlen(s2); 23 for(i = 1; i <= len1; ++i) 24 for(j = 1; j <= len2; ++j) 25 { 26 if(s1[i-1] == s2[j-1]) 27 dp[i][j] = dp[i-1][j-1] + 1; 28 else 29 dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 30 } 31 32 printf("%d ", dp[len1][len2]); 33 } 34 return 0; 35 }