作者在 2010-12-29 12:41:37 发布以下内容
传说中，月老是掌管男女婚姻之神。每年七夕，七星娘娘会把人世间未婚的成年男女制成名册，向天庭呈报。月下老人收到名册后，按照个性、善恶、兴趣与条件抄写成一本配偶名册，然后用红线绑牢男女二人之足，使合适的男女配成一对佳偶。
在一个古老的小镇，有一条古老的小河横穿这个镇南北，把这个小镇划分成东西两个部分。这个古老的小镇保留着一个古老的风俗，所有未婚男子都住在这条河的西岸上面，所有的未婚女子都住在这条河的东岸。
今年月下老人收到了这个小镇上所有未婚男女的名册，他把每个人的个性、善恶、兴趣与条件做了一个简单的汇总，给每个人添加了一个如A B C之类的标签，只有相同标签的男女才有可能用红线绑在一起。原本这个是个很简单的事情，但是现在问题是月老使用的红线，是不能互相交叉的，否则后果会很严重。所以月老为了更多人的幸福，他只能牺牲部分人的幸福。现在月老在纸上笔划了很久，还是没能比划出一个最好的方案，使得让最多对情侣终成眷属。您能帮帮他么？
Input
输入的文件的第一行包含两个整数N,M(0<N, M <= 1000)，分别表示未婚男子和未婚女子的数目。
第二行包含一个长度为N的字符串，字符串为大写字母A-Z和小写字母a-z组成，从北到南顺序表示每个男子的标签。
第三行包含一个长度为M的字符串，从北到南顺序顺序表示每个女子的标签。
Output
输出一个整数表示月老最多可以为多少对情侣成功牵线。
Sample Input
5 4
ABACB
CBAB
Sample Output 3
#include <iostream>
using namespace std;
char a[1001],b[1001];
int t[1001][1001];
int n,m;
void lcs()
{
int i,j;
for(i=0;i<=n;i++)
t[i][0]=0;
for(j=0;j<=m;j++)
t[0][j]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i]==b[j])
t[i][j]=t[i-1][j-1]+1;
else if(t[i-1][j]>t[i][j-1])
t[i][j]=t[i-1][j];
else
t[i][j]=t[i][j-1];
cout<<t[n][m]<<endl;
}
int main()
{
int i;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=m;i++)
cin>>b[i];
lcs();
return 0;
}
using namespace std;
char a[1001],b[1001];
int t[1001][1001];
int n,m;
void lcs()
{
int i,j;
for(i=0;i<=n;i++)
t[i][0]=0;
for(j=0;j<=m;j++)
t[0][j]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i]==b[j])
t[i][j]=t[i-1][j-1]+1;
else if(t[i-1][j]>t[i][j-1])
t[i][j]=t[i-1][j];
else
t[i][j]=t[i][j-1];
cout<<t[n][m]<<endl;
}
int main()
{
int i;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=m;i++)
cin>>b[i];
lcs();
return 0;
}