hdu1159 参考答案

   1 /*
   2 经典DP：LCS，最长公共子列
   3 zju 1733 hdu 1159 Common Subsequence
   4 ymc 2008/09/22
   5 题目大意：
   6 给定两个字串窜S与T，求S与T的最长公共子列。
   7 分析与解题大意：
   8 令ans[i][j]为S的前i个字符与T的前j个字符的最长公共字串的
   9 长度。则有
  10 若S[i-1]==T[j-1],则ans[i][j]=ans[i-1][j-1]+1;
  11 否则,ans[i][j]=Max{ans[i-1][j],ans[i][j-1]}。
  12 S与T的最长公共子列的长度为ans[n][m]，其中n,m分别为
  13 S与T的长度。
  14 */
  15 #include <iostream>
  16 #include <string>
  17 using namespace std;
  18 const int N=1000;
  19 char s[N],t[N];
  20 int ans[N][N];
  21 inline int Max(int x,int y)
  22 {
  23     return x>y?x:y;
  24 }
  25 void LCS()
  26 {
  27     int n=strlen(s);
  28     int m=strlen(t);
  29     memset(ans,0,sizeof(ans));
  30     for(int i=1;i<=n;i++)
  31         for(int j=1;j<=m;j++)
  32         {
  33             if(s[i-1]==t[j-1])
  34             {
  35                 ans[i][j]=ans[i-1][j-1]+1;
  36             }
  37             else
  38                 ans[i][j]=Max(ans[i-1][j],ans[i][j-1]);
  39         }
  40     printf("%d\n",ans[n][m]);
  41 }
  42 int main()
  43 {
  44     while(scanf("%s %s",s,t)!=EOF)
  45     {
  46         LCS();
  47     }
  48 }

   1 //722801 2008-07-26 11:50:30 Accepted 1159 265MS 3908K 788 B G++ whiteTiger DP
   2 #include <stdio.h>
   3 #include <string.h>
   4 
   5 int lcsCount[1001][1001];
   6 char a[1001],b[1001];
   7 
   8 int max(const int x, const int y){
   9     return x>y?x:y;
  10 }
  11 
  12 void lcs(){
  13     memset(lcsCount, 0, sizeof(lcsCount));
  14     int x = strlen(a);
  15     int y = strlen(b);
  16     for(int i = 0; i <= x; i++){
  17         for(int j = 0; j <= y; j++){
  18             if(i==0 || j ==0)
  19                 lcsCount[i][j] = 0;
  20             else if(a[i-1] == b[j-1])
  21                 lcsCount[i][j] = lcsCount[i-1][j-1]+1;//状态转移方程
  22             else{
  23                 lcsCount[i][j] = max(lcsCount[i][j-1], lcsCount[i-1][j]);//状态转移方程
  24             }
  25         }
  26     }
  27 }
  28 
  29 int main()
  30 {
  31     while(scanf("%s %s", a, b)!=EOF){
  32         lcs();
  33         printf("%d\n", lcsCount[strlen(a)][strlen(b)]);
  34     }
  35 
  36     return 0;
  37 }