设为首页 加入收藏

TOP

HDU 1503 Advanced Fruits （LCS，DP）
2015-07-20 17:56:22 来源: 作者: 【大 中 小】 浏览:4次
Tags：HDU 1503 Advanced Fruits LCS



题意：给你两字符串s1，s2，用最短的字符串表示他们（公共字串输出一次）。


Sample Input 
apple peach
ananas banana
pear peach

Sample Output 
appleach
bananas
pearch

dp[i][j] : 第一个字符串的前 i 个 ，和第二个字符串的前 j 个最短组合的长度 。


pre[i][j] : 第一个字符串的第 i 个 ，和第二个字符串的第 j 个字符的状态。 


#include
  
   
#include
   
     #include
    
      #include
     
       #include
       #include
       
         #include
        
          #include 
         
           #include 
          
            #include
           
             #include
            
              using namespace std; #define INF 1e8 #define eps 1e-8 #define LL long long #define N 105 #define mod 1000000007 char a[N],b[N],str[N]; int c[N][N],pre[N][N],m,n; void lcs(char *a,char *b,int c[][N]) { int i,j; for(i=0;i<=m;i++) c[i][0]=i,pre[i][0]=3; for(j=0;j<=n;j++) c[0][j]=j,pre[0][j]=1; for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { if(a[i-1]==b[j-1]) c[i][j]=c[i-1][j-1]+1,pre[i][j]=2; //表示pre[i][j]由a[i-1]或b[i-1]而来 else if(c[i-1][j]>=c[i][j-1]) c[i][j]=c[i][j-1]+1,pre[i][j]=1; //pre[i][j]由b[j-1]而来 else c[i][j]=c[i-1][j]+1,pre[i][j]=3; //pre[i][j]由a[i-1]而来 } } } void out(int i,int j) { if(i==0&&j==0) return; if(pre[i][j]==2) { out(i-1,j-1); printf("%c",a[i-1]); } else if(pre[i][j]==3) { out(i-1,j); printf("%c",a[i-1]); } else { out(i,j-1); printf("%c",b[j-1]); } } int main() { while(~scanf("%s%s",a,b)) { m=strlen(a);n=strlen(b); lcs(a,b,c); out(m,n); printf("\n"); } return 0; }


【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：uva 10288 - Coupons(概率) 下一篇：uva 12230 - Crossing Rivers(概..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: