pku 1458_DP - wyiu

C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合

:: 管理

posts - 100, comments - 15, trackbacks - 0

//标准LCS，把一个j写成i导致3RE，o(╯□╰)o

#include<iostream>

#include<string>

using namespace std;

#define M 800

char stra[M+1];

char strb[M+1];

int cs[M+1][M+1];

int m,n;

void LCS()

{

int i,j;

m=strlen(stra+1);

n=strlen(strb+1);

for(i=0;i<=m;i++)

cs[i][0]=0;

for(j=0;j<=n;j++)

cs[0][j]=0;

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

if(stra[i]==strb[j]) cs[i][j]=cs[i-1][j-1]+1;

else cs[i][j]=max(cs[i-1][j],cs[i][j-1]);

}

int main()

{

while(scanf(" %s %s",stra+1,strb+1)!=EOF)

{

LCS();

printf("%d\n",cs[m][n]);

}

return 0;

}

posted on 2009-05-20 13:45 wyiu 阅读(82) 评论(0) 编辑收藏引用所属分类: POJ

只有注册用户登录后才能发表评论。


相关文章: poj 1061 线性同余 poj 2115 线性同余 poj 3368 rmq(st) poj 3264 RMQ poj 2352 树状数组 poj 1469 二分匹配 poj 2186 有向图强连通分支 poj 2239 二分图最大匹配 poj 3748 位运算 poj 2724 二分匹配

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

随笔分类(84)