poj 1458 输出最长子序列长度和具体的最长子序列

//解释：
因为每个c[i][j]的项只依赖于表c中的其他三项:c[i-1][j-1],c[i-1][j],c[i][j-1];
所以，可以引入标志数组b[i][j]来标志计算c[i][j]时所选择的项。

#include<iostream>
using namespace std;

//***************************常量定义***************************

 const int MAX_LENGHT=500;
//**************************题目变量****************************
//全局变量全部初始化为0
 char X[MAX_LENGHT];
 char Y[MAX_LENGHT];

//*************************算法变量*****************************
 //全局变量全部初始化为0
 int c[MAX_LENGHT][MAX_LENGHT];//c[i][j]表示Xi与Yj的一个LCS

 int b[MAX_LENGHT][MAX_LENGHT];//b[i][j]指向的表项对应计算从c[i][j]时所选择的子问题的最优解
                               //b[i][j]=1(c[i][j]=c[i-1][j-1]+1) b[i][j]=2(c[i][j]=c[i-1][j]) b[i][j]=3(c[i][j]=c[i][j-1])


void LCS_LENGTH(int m,int n)
{  

   for(int i=1;i<=m;i++)
   {
   for(int j=1;j<=n;j++)
   {
   if(X[i-1]==Y[j-1])
   {
  c[i][j]=c[i-1][j-1]+1;
  b[i][j]=1;
   }   
   else 
   if(c[i][j-1]>=c[i-1][j])
   {
  c[i][j]=c[i][j-1];
  b[i][j]=3;
   }
   else
   {
  c[i][j]=c[i-1][j];
  b[i][j]=2;
   }
   }
   }
   cout<<c[m][n]<<endl;
}

void PrintLcs(int m,int n)
{
if((m==0)||(n==0)) return;
if(1==b[m][n]) 
{
  PrintLcs(m-1,n-1);
  cout<<X[m-1]<<" ";
}
else
if(2==b[m][n])
{
PrintLcs(m-1,n);
}
else
{
PrintLcs(m,n-1);
}
}
int main()
{

while(scanf("%s %s",X,Y)!=EOF)
{ 
    int m=strlen(X);
        int n=strlen(Y);
LCS_LENGTH(m,n);
PrintLcs(m,n);
}
return 0;
}