"hdu1159 参考答案"版本比较

   1 //written by czy dp(LCS)
   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 }