xmu1030 月老的难题

时间：2010-05-18 来源：hbj_2008

题目大致意思：

有1,2 两行字符，第一行中的字符与第二行红相同的字符用线相连，但线不能交叉，问题是求着两行字符中最多能有多少对？？

这应该是动态规划中构造最长子序列。

X=x1 x2 x3…..xn; Y =y1 y2 y3…..ym;

if (xn==ym) L(n,m) = L(n-1,m-1)+1; //两序列都退一格，继续比较

else L(n,m) = max[L(n-1,m),L(n,m-1)] ; //两序列分别退一行，并比较两者取大值

在计算中，为了避免重复计算，在L（n,m）中把中间值记录下来

把从1到n行和从1到m列，都遍历计算；

L(i,0)=0 i=0:n ; L(0,j) =0 , j=0;m

for i=1 : n;

for j=1 : m

if(x[i]==y[j]) L(i,j)=L(i-1,j-1) +1 ;

else L(i,j)=max[L(i-1,j),L(i,j-1)] ;

提交代码：

#include<iostream>
#include<cstdlib>
#define max 1002
int a[max][max];
using namespace std ;
int main()
{
    int n1 , n2 ;
    cin>>n1 >>n2 ;
    char* p1 = new char[n1];
    char* p2 = new char[n2];
    int i =0 ;
    while(i<n1)
    cin>>p1[i++];
    i=0;
    while(i<n2)
    cin>>p2[i++];
    for(int j=0;j<max;j++)
    a[0][j]=0;
    for(i=0;i<max;i++)
    a[i][0]=0;
    for(int i=1;i<=n1;i++)
       for(int j=1;j<=n2;j++)
           if(p1[i-1]==p2[j-1])
               a[i][j]=a[i-1][j-1]+1;
           else {
                   if(a[i-1][j]>a[i][j-1])
                     a[i][j]=a[i-1][j];
                   else a[i][j]=a[i][j-1];
                }
    cout<<a[n1][n2];
    cout<<endl;
    system("pause");
    return 0 ;
}