FAFU OJ 依旧水水的dp3

依旧水水的dp3

Time Limit:	1000MS	Memory Limit:	65536KB
Total Submissions:	121	Accepted:	57

Share Description:       子序列——对于一个给定序列X=<x1,x2,…,xm>，其子序列就是指该序列中的若干个元素构成的一个序列，这些元素可以不是连续的，但其先后顺序必须与原序列相同。 

      对于两个给定序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>，若存在某个序列Z=<z1,z2,…,zk>，既是X的子序列，也是Y的子序列，则称其为X和Y的公共子序列(LCS)，所有公共子序列中最长的序列称为最长公共子序列。 

      给出两个只包含大写英文字母字符序列X和Y，求出它们的最长公共子序列的长度。 

       Input: 第一行一个字符串X。 

      第二行一个字符串Y。 

      数据保证字符串的长度不大于1000。 

       Output: 一个整数，即最长公共子序列的长度。 Sample Input: ABCBDAB BDCBA Sample Output: 4 Source:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1005

char a[N],b[N];
int d[2][N];

int main()
{
	scanf("%s%s",a + 1,b + 1);
	int l1 = strlen(a + 1);
	int l2 = strlen(b + 1);
	memset(d,0,sizeof(d));
	int t = 0;
	for(int i = 1; i <= l1; i++)
	{
		t=1-t;
		for(int j = 1; j <= l2; j++)
			if(a[i] == b[j])
				d[t][j] = d[1 - t][j - 1] + 1;
			else
				d[t][j] = max(d[1 - t][j],d[t][j - 1]);
	}
	cout << d[t][l2] << endl;
	return 0;
}