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;
}