hdu1501 Zipper[簡單DP]

目錄

• 題目位址
• 題幹
• 代碼和解釋
• 參考

hdu1501

最優子結構分析：設這三個字元串分别為a、b、c，如果a、b可以組成c，那麼c的最後一個字母必定來自a或者b的最後一個字母。c去除最後一位，就變成由a-1和b或者a和b-1構成c-1的問題。

狀态轉移方程：DP[i][j]表示c中i個字元來自于a，j個字元來自于b，即由a的前i個字元和b的前j個字元組成c的前i+j個字元。DP[i][j]為1則真，為0則假。

/*給3個字元串，讓你判斷能不能組合前兩個字元串來獲得第3個字元串。前兩個字元串可以被任意混合，但都必須保持原來的順序。*/
/*輸入：第一行輸入一個1到1000的整數，表示樣例的數量。一組樣例一行。
字元串都隻包含大小寫字母，第3個字元串的長度必須等于前兩個字元串長度之和，前兩個字元串長度從1到200*/
/*輸出：
Data set n: yes或Data set n: no，每組樣例有一個輸出。*/
#include<stdio.h>
#include<string.h>
int main()
{
    int T;
    char a[210];
    char b[210];
    char c[410];
    int len1,len2;
    int DP[210][210];//DP[i][j]指c中有i位來自a，j位來自b 
    int i,j;
    int count = 1;
    scanf("%d",&T);
    while(T--){
        scanf("%s%s%s",a+1,b+1,c+1);
        len1=strlen(a+1);
        len2=strlen(b+1);
        memset(DP,0,sizeof(DP));
		
        for(i=1;i<=len1;i++){
            if(a[i]==c[i]){
                DP[i][0]=1;
                }
        }
		
        for(j=1;j<=len2;j++){
            if(b[j]==c[j]){
                DP[0][j]=1;
            }
        }
		
        for(i=1;i<=len1;i++){
            for(j=1;j<=len2;j++){
                if((DP[i-1][j]&&a[i]==c[i+j])||(DP[i][j-1]&&b[j]==c[i+j])){
                    DP[i][j]=1;
                }
            }
        }
		
        if(DP[len1][len2]==1){
            printf("Data set %d: yes\n",count);
        }
        else printf("Data set %d: no\n",count);
        count++;
    }
    return 0;
} 
           

這裡的字元串輸入是scanf("%s",a+1);而不是scanf("%s",a);我認為是為了友善了解第幾位就是第幾位，而且友善對DP[i][0]和DP[0][j]的處理。

注意幾個字元串數組都要開的大一點，一開始我wa就是因為數組開成201，不夠大。

hdu1501最優子結構

hdu1501簡單DP

STAY. you have NO WHERE TO GO. try to live it well. for you have only ONE life.