某山寨

z4zr的待调教小窝

POJ2250 Compromise DP LCS(最长公共子序列)

Tag:dp lcs poj

POJ2250 Compromise DP LCS(最长公共子序列)

http://poj.org/problem?id=2250
题目大意
输入两组大量的单词 单词数小于100 每个单词长度小于30 每组单词遇到# 算输入完毕
顺序输出两组单词中序列相同的单词

额描述很简短。。。。

刚刚看到题目,第一感觉像模拟题。。。。不过此题模拟似乎会错解 因为“最长”

下面开始思考吧:

定义2个二位数组 用来存储两组字符串
str1102 str2102
定义两个整形 存储每组单纯的数量 str1_size str2_size

(新学C语言的童鞋一定要从开始就养成合理定义变量名字的好习惯,推荐大家看高质量C_C++编程这本书,好的编程风格是迈向成功的第一步,记得看2012年的wordfinal的时候 发现了一个问题 咱们中国的大神们似乎在长代码的调试能力上弱弱。。 额 他们的代码一般风格很好 结构清晰 但是调试也很困难,想想如果代码写的跟鸟巢一样的乱 还怎么调试?不要认为一次敲代码就AC 很厉害 早晚会有调试的时候)

定义dp数组 dp102
把每个单词当作状态的节点
如果str1[i]==str2[j] dpi=dpi-1+1
如果str1[i]!=str2[j] dpi=max(dpi,dpi-1)
这样我们就能找到最长的那个单词组的序列了

下面遇到了如何去输出这个序列的问题了。。。。
从头来一个一个判定单词是不是这个最长子序列中似乎很麻烦 额。。。没敢想。。
由于dpstr1_size-1这个位置存储的是最长子序列的长度 额 我们可以从尾部向前读取存入栈中。
额 但是我们无法确定 它的上一个元素是哪个。。

加一个数组标记一下吧。。。 于是诞生了opt这个数组 opt102
由opt这个数组来存储所当前状态采用的方向
这样我们的核心部位需要有所修改了哈~
如果str1[i]==str2[j]

 dp[i][j]=dp[i-1][j-1]+1
 并且opt[i][j]=upleft

如果str1[i]!=str2[j]

 dp[i][j]=max(dp[i][j-1],dp[i-1][j])
 opt[i][j]=max所取值所在的位置up 或者left

这样我们就记录的单词路径

现在我们就可以从dpstr1_size-1开始寻找最长序列的每一个元素
如果 opti存储的时upleft的时候将这个单词存入栈中
其他的时候 就把i j 指向对应的上一个节点
当i=j=0的时候 就完毕了 当然这里可以优化一下 做题的时候没有想到这个问题。。。
看来写博客也是有好处的。。。。。
优化是什么? 优化就是 当dpi==1的时候我们就不需要接着找了前面一定没有我们要找的单词了

最后从栈中输出答案就可以了

P.S.栈是什么?
如果没有学过数据结构 很有可能不知道。。当然学过数据结构 也可以不知道。。。。。
一句话 栈 就是先进后出的东西。。。。。
就是先进去的后出来
eg: 1 2 3 按照顺序入栈

出去的时候 按照 3 2 1 的顺序出去了。。。。
//476K  16MS  G++
#include<stdio.h>
#include<string.h>
enum Opt{ul=1,up=2,left=3};//这里用了,方便理解和写程序。。。
char str1[102][32],str2[102][32];//两个人的单词
int dp[102][102];//单词的路径
int opt[102][102];//单词的方向
int ans[100];//用数组模拟的栈。。
int str1_size,str2_size;

int main(){
    int i,j,k;
    while(scanf("%s",str1[0])!=EOF){
        memset(dp,0,sizeof(dp));
        memset(opt,0,sizeof(opt));
        str1_size=str2_size=0;
        while(str1[str1_size++][0]!='#'){
            scanf("%s",str1[str1_size]);
        }
        str1_size--;
        while(scanf("%s",str2[str2_size])){
            if(str2[str2_size++][0]=='#')break;
        }
        str2_size--;
        //下面就是核心了 dp开始
        for(i=0;i<str1_size;i++){
            for(j=0;j<str2_size;j++){
                if(strcmp(str1[i],str2[j])==0){
                    dp[i][j]=dp[i-1][j-1]+1;
                    opt[i][j]=ul;
                }
                else{
                    if(dp[i-1][j]>dp[i][j-1]){
                        dp[i][j]=dp[i-1][j];
                        opt[i][j]=up;
                    }
                    else{
                        dp[i][j]=dp[i][j-1];
                        opt[i][j]=left;
                    }
                }
            }
        }
        i=str1_size-1;
        j=str2_size-1;
        k=0;
        //接下来是原路返回吧单纯的下标存入栈中。。。。
        while(i>=0&&j>=0){
            if(opt[i][j]==ul){
                ans[k++]=i;
                i--;j--;
            }
            else if(opt[i][j]==up){
                    i--;
                }
            else j--;
        }
       //最重要的地方。。。。。。输出哈~不然怎么AC?
        for(i=k-1;i>0;i--){
            printf("%s ",str1[ans[i]]);
        }
        printf("%s\n",str1[ans[i]]);
    }
    return 0;
}

添加新评论

文章二维码