程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 1503 最大公共子序列+輸出路徑

hdu 1503 最大公共子序列+輸出路徑

編輯:C++入門知識

hdu 1503 最大公共子序列+輸出路徑


 

 

#include
#include
#include
using namespace std;

int max(int a,int b)
{
    return a>a?a:b;
}
char str1[110],str2[110];
int mark[110][110];
int deal(int i,int j)
{
   
    if(i==0&&j==0) return 0;
    if(mark[i][j]==0)
    {
        deal(i-1,j-1);
        printf("%c",str1[i-1]);
    }    
    else if(mark[i][j]==1)
    {
        deal(i-1,j);
        printf("%c",str1[i-1]);
    }
    else if(mark[i][j]==2)
    {
        deal(i,j-1);
        printf("%c",str2[j-1]);
    }
    return 0;
}
int main()
{
    
    int i,j;
    int dp[110][110];
    while(~scanf("%s%s",str1,str2))
    {
        int len1=strlen(str1);
        int len2=strlen(str2);
        memset(dp,0,sizeof(dp));
         for(i = 0;i<=len1;i++)  
        mark[i][0] = 1;  
        for(i = 0;i<=len2;i++)  
        mark[0][i] = 2;  
        for(i=1;i<=len1;i++)
        {
            for(j=1;j<=len2;j++)
            {
                if(str1[i-1]==str2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                    mark[i][j]=0;
                }
                else 
                {
                    //dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                    if(dp[i-1][j]>=dp[i][j-1])
                    {
                        dp[i][j]=dp[i-1][j];
                        mark[i][j]=1;
                    }
                    else 
                    {
                        mark[i][j]=2;
                        dp[i][j]=dp[i][j-1];
                    }
                }
            }
        }
        //printf("****\n");
        deal(len1,len2);
        printf("\n");
    }
    return 0;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved