xmu1030月老的难题

时间：2010-08-02 来源：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)] ;

提交代码：

01    #include<iostream>
02    #include<cstdlib>
03    #define max 1002
04    int a[max][max];
05
06    using namespace std ;
07
08    int main()
09    {
10     int n1 , n2 ;
11     cin>>n1 >>n2 ;
12     char* p1 = new char[n1];
13     char* p2 = new char[n2];
14     int i =0 ;
15     while(i<n1)
16     cin>>p1[i++];
17     i=0;
18     while(i<n2)
19     cin>>p2[i++];
20     for(int j=0;j<max;j++)
21     a[0][j]=0;
22     for(i=0;i<max;i++)
23     a[i][0]=0;
24     for(int i=1;i<=n1;i++)
25     for(int j=1;j<=n2;j++)
26     if(p1[i-1]==p2[j-1])
27     a[i][j]=a[i-1][j-1]+1;
28     else {
29     if(a[i-1][j]>a[i][j-1])
30     a[i][j]=a[i-1][j];
31     else a[i][j]=a[i][j-1];
32     }
33     cout<<a[n1][n2];
34     cout<<endl;
35     system("pause");
36     return 0 ;
37    }