HDU-1159 Common Subsequence

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1159

题意：多组输入，每组两个字符串，求最长公共子序列(LCS)的长度

思路：裸题，套板子。dp[i][j]表示a串以i结尾，b串以j结尾的范围中，LCS的长度，如果a[i]=b[j]，那么dp[i][j]=dp[i-1][j-1]+1,不然就从dp[i-1][j]和dp[i][j-1]里挑一个最大的，遍历i和j跑一遍最后输出dp[n][m]就好了

代码：

 1 #include<bits/stdc++.h>
 2 // #include<iostream>
 3 // #include<cstdio>
 4 // #include<cmath>
 5 #define inf 0x3f3f3f3f
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 typedef long double ld;
10 
11 const int M = int(1e5)*3 + 5;
12 const int mod = 10056;
13 
14 inline int lowbit(int x) {
15     return x & (-x);
16 }
17 
18 // string a,b;
19 char a[M],b[M];
20 int dp[1005][1005];
21 int main(){
22     while(~scanf("%s%s",a+1,b+1)){
23         memset(dp,0,sizeof(dp));
24     
25         int n=strlen(a+1);
26         int m=strlen(b+1);
27         
28         for(int i=1;i<=n;i++){
29             for(int j=1;j<=m;j++){
30                 if(a[i]==b[j]){
31                     dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
32                 }
33                 else{
34                     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
35                 }
36             }
37         }
38         
39         cout<<dp[n][m]<<endl;
40     }
41     // scanf("%s",a+1);
42     // int n=strlen(a+1);
43     // printf("%d",n);
44     return 0;
45 }