ACM PKU 1458 Common Subsequence 经典且简单动态规划

http://acm.pku.edu.cn/JudgeOnline/problem?id=1458
当初看<算法导论>的时候觉得这很神奇,题做多了,反而觉得很容易了. 这都是菜题,不是我们的目标.
Source Code

Problem: 1458  User: lnmm 
Memory: 856K  Time: 0MS 
Language: C++  Result: Accepted 

Source Code 
#include"stdio.h"
#include"string.h"
#define MAX 1000
char sz1[MAX],sz2[MAX];
int aMaxLen[MAX][MAX];
void main()
{
    while(scanf("%s%s",sz1+1,sz2+1)!=EOF)
    {
        int len1,len2;
        len1=strlen(sz1+1);
        len2=strlen(sz2+1);
    
        int i,j;
        for(i=0;i<len1;i++)aMaxLen[i][0]=0;
        for(j=0;j<len1;j++)aMaxLen[0][j]=0;
        for(i=1;i<=len1;i++)
            for(j=1;j<=len2;j++)
                if(sz1[i]==sz2[j])
                    aMaxLen[i][j]=1+aMaxLen[i-1][j-1];
                else aMaxLen[i][j]=aMaxLen[i-1][j]>aMaxLen[i][j-1]?aMaxLen[i-1][j]:aMaxLen[i][j-1];
        printf("%d\n",aMaxLen[len1][len2]);


    }
}

posted on 2007-11-15 14:56 流牛ζ木马 阅读(2146) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2007年9月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

导航

统计

公告

MY Email/MSN :mars1021@163.com QQ : 27402040 流牛ζ木马

常用链接

留言簿(6)

随笔档案

相册

搜索

最新随笔

最新评论

阅读排行榜

评论排行榜