题目的意思是给你三个字符串,第三个字符串要由前面两个字符串组成,并且前面两个字符串里面的字符顺序要和原来的一样。

这个题dp方法有多种。

代码1:

StatusAccepted
Time46ms
Memory1892kB
Length985
LangC++
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=205;
int dp[maxn][maxn], n, len1,len2,len3;
char s1[maxn], s2[maxn], s3[maxn];
int main()
{
    scanf("%d", &n);
    for(int cas=1;cas<=n;cas++){
        scanf("%s%s%s", &s1[1], &s2[1], &s3[1]);
        s1[0]=s2[0]=s3[0]='0';
        len1=strlen(s1)-1;len2=strlen(s2)-1;len3=strlen(s3)-1;
        memset(dp, -1, sizeof(dp));
        dp[0][0]=0;
        for(int i=0;i<=len1;i++){
            for(int j=0;j<=len2;j++){
                if(dp[i][j]!=-1){
                    if(s2[j+1]==s3[dp[i][j]+1]){
                        dp[i][j+1]=dp[i][j]+1;
                    }
                    if(s1[i+1]==s3[dp[i][j]+1]){
                        dp[i+1][j]=dp[i][j]+1;
                    }
                }
            }
        }
        if(dp[len1][len2]==len3){
            printf("Data set %d: yes\n", cas);
        }
        else printf("Data set %d: no\n", cas);
    }
    return 0;
}

代码2:

StatusAccepted
Time62ms
Memory1892kB
Length812
LangC++
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=205;
int dp[maxn][maxn], n, len1,len2,len3;
char s1[maxn], s2[maxn], s3[maxn];
int main()
{
    scanf("%d", &n);
    for(int cas=1;cas<=n;cas++){
        scanf("%s%s%s", s1+1, s2+1, s3+1);
        s1[0]=s2[0]=s3[0]='0';
        len1=strlen(s1)-1;len2=strlen(s2)-1;len3=strlen(s3)-1;
        memset(dp, 0, sizeof(dp));
        for(int i=1;i<=len1;i++){if(s1[i]==s3[i])dp[i][0]=1;}
        for(int j=1;j<=len2;j++){if(s2[j]==s3[j])dp[0][j]=1;}
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                dp[i][j]=((dp[i-1][j]&&s1[i]==s3[i+j])||(dp[i][j-1]&&s2[j]==s3[i+j]));
            }
        }
        printf("Data set %d: %s\n", cas, dp[len1][len2]?"yes":"no");
    }
    return 0;
}