【POJ2250】Compromise (最长公共子序列,DP)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 21 日

POJ上边一直WA啊,找N久N久,找不到错误,看到的人求教育我啊。、。。。。

#include<cstdio>  
#include <string>  
#include <iostream>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
int reslen[301][301];  
int respos[300][301];  
string st1[101],st2[101],resst[101];  
int main(){  
    freopen("1.txt","r",stdin);  
    int i,x,y,st1len,st2len;  
    while(!cin.eof()){  
        memset(reslen,0,sizeof(reslen));  
        memset(respos,1,sizeof(respos));  
        i=0;  
        while(cin>>st1[i]){  
            if(st1[i]=="#"){  
                st1len=i;  
                break;  
            }  
            i++;  
        }  
        i=0;  
        while(cin>>st2[i]){  
            if(st2[i]=="#"){  
                st2len=i;  
                break;  
            }  
            i++;  
        }  
        for ( x=0;x<st1len;x++){  
            for ( y=0;y<st2len;y++){  
                if(st1[x]==st2[y]){  
                    reslen[x+1][y+1]=reslen[x][y]+1;  
                    respos[x+1][y+1]=2;  
                }  
                else{  
                    if(reslen[x][y+1]>reslen[x+1][y]){  
                        reslen[x+1][y+1]=reslen[x][y+1];  
                        respos[x+1][y+1]=3;  
                    }  
                    else {  
                        reslen[x+1][y+1]=reslen[x+1][y];  
                        respos[x+1][y+1]=1;  
                    }  
                }  
            }  
        }  
        x=st1len;y=st2len;  
        i=0;  
        while(1)  
        {  
            if(respos[x][y]==1)  
                y--;  
            else if(respos[x][y]==2)  
            {  
                resst[i++] =st1[x-1];  
                x--,y--;  
            }else if(respos[x][y]==3)  
                x--;  
            if(x<=0 || y<=0) break;  
        }  
        int first=1;  
        while(i--)  
            if(first){cout<<resst[i];first=0;}  
            else cout<<" "<<resst[i];  
        cout<<endl;  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日