Sicily 1010 Zipper

1826 단어
제목 대의: 문자열 1과 문자열 2의 원래 문자 순서를 유지하는 전제에서 문자열 1과 문자열 2를 문자열 3으로 연결할 수 있는지 판단할 세 개의 문자열을 제시한다.
사고방식:DP, 2차원 그룹 dp[][], dp[i][j]는str1의 전 i 문자가str2의 전 j 문자와str의 전 i+j 문자를 구성할 수 있는지를 나타낸다.또한 i=0 또는 j=0은 빈 문자열을 표시하므로 dp를 초기화할 때 주의해야 한다.증명 가능: dp[i-1][j](dp[i][j]위 한 칸)과 dp[i][j-1](dp[i][j]왼쪽 한 칸)이 모두 0이면 dp[i][j]는 0이다.dp[i-1][j](dp[i][j]위 칸)이 1이고 왼쪽 자모가str[i+j]일 때, 또는 dp[i][j-1](dp[i][j]왼쪽 칸)이 1이고 위 자모가str[i+j]일 때 dp[i][j]가 1이다.
#include <stdio.h>
#include <string.h>
char str1[220];
char str2[220];
char str[420];
int dp[220][220];
int main()
{
    int t,i,j,k,ctr;
    int length1,length2;

    scanf("%d",&t);
    for (ctr=1;ctr<=t;ctr++) {
        scanf("%s%s%s",&str1,&str2,&str);
        length1=strlen(str1);
        length2=strlen(str2);
        dp[0][0]=1;
        for (i=1;i<=length1;i++) {
            if (dp[0][i-1]==1&&str1[i-1]==str[i-1])
                dp[0][i]=1;
            else 
                dp[0][i]=0;
        }
        for (i=1;i<=length2;i++) {
            if (dp[i-1][0]==1&&str2[i-1]==str[i-1])
                dp[i][0]=1;
            else
                dp[i][0]=1;
        }
        for (i=1;i<=length2;i++) {
            for (j=1;j<=length1;j++) {
                dp[i][j]=0;
            }
        }
        for (i=1;i<=length2;i++) {
            for (j=1;j<=length1;j++) {
                if ((dp[i][j-1]==1&&str1[j-1]==str[i+j-1])||(dp[i-1][j]==1&&str2[i-1]==str[i+j-1]))
                    dp[i][j]=1;
            }
        }
        printf("Data set %d: ",ctr);
        if (dp[length2][length1]==1)
            printf("yes
"); else printf("no
"); } return 0; }

좋은 웹페이지 즐겨찾기