poj 1159 Common Subsequence LCS模板

题意：给两个串，求出他们LCS的长度

LCS（Longest Common Subsequence）最长公共子序列：一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列

X={x1，x2，x3...xn}，Y={y1,y2，y3...ym} ，令Z={z1，z2，z3...zk}是他们的LCS

i=1,2,3,4...n。  j=1,2,3,4...m 。Xi={x1,x2,x3...xi}，Yi={y1,y2,y3...yj}，Zk={z1,z2,z3...zk}

1）若xn=ym，则zk=xn=ym，Zk-1为Xn-1,和Ym-1的LCS

2）若xn!=ym，那么xn!=zk意味着Z是Xi-1和Y的LCS

3）若Xn!=ym，那么ym!=zk意味着Z是X和Yj-1的LCS

证明：

1）

Xn=ym，如果zk!=xn，那么可以在Z的后面加上xn，这时便于假设Z为LCS相矛盾，因为在Z后面再加

一个xn使得长度比Z多1，得到的这个公共子序列才是最长的。

2）

xn!=ym，xn!=zk。Z是Xi-1和Y的LCS，假设存在长度大于Z的公共子序列W是Xi-1和Y的LCS，那么W也是

X和Y的LCS，与假设Z（Z的长度为k，W长度大于K）是X和Y的LCS矛盾。

3）

同2）。

最优子结构

如果xn=ym，那么求解Xn-1和Ym-1的LCS，否则求解问题1.（Xn-1和Y的LCS）2.（Xn和Ym-1的LCS），取其中长度大的。

用c[I][j]表示Xi和Yj的LCS的长度

状态方程：

                    0                                           i=0或j=0

c[i][j]=          c[i-1][j-1]+1                           xi=yj

                    Max(c[i-1][j],c[i][j-1])             xi!=yj

模板题：hdu 1159

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#define Max(a,b) a>b?a:b
using namespace std;
int c[500][500];
int main()
{
	//freopen("in.txt","r",stdin);
	string a,b;
	while(cin>>a>>b)
	{
		int n,m;
		n=a.size();m=b.size();
		memset(c,0,sizeof(c));
		for(int i=0;i<n;i++)
			c[i][0]=0;
		for(int i=0;i<m;i++)
			c[0][i]=0;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(a[i-1]==b[j-1])
			c[i][j]=c[i-1][j-1]+1;
			else
			c[i][j]=Max(c[i-1][j],c[i][j-1]);
		}
		cout<<c[n][m]<<endl;
	}
}