1501 zipper.cpp

ACM 威士忌部分答案

/*
1501 Zipper
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 256 K

GUN C++
*/
//DP
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

const int Max=201;

char in1[Max],in2[Max],zip[2*Max];
bool F[Max][Max];
int len1,len2;

int solve()
{
    int i,j;
    
    if(in1[0]==zip[0])
        F[1][0]=true;
    if(in2[0]==zip[0])
        F[0][1]=true;
    i=j=1;
    while(i<=len1)
        if(in1[i]==zip[i] && F[i][0]==true)
        {   F[i+1][0]=true;i++;}
        else
            break;
    while(j<=len2)
        if(in2[j]==zip[j] && F[0][j]==true)
        {   F[0][j+1]=true;j++;}
        else
            break;

    for(i=1;i<=len1;i++)
        for(j=1;j<=len2;j++)
        {
            F[i][j] = (F[i-1][j] && (in1[i-1] == zip[i+j-1])) || (F[i][j-1] && (in2[j-1] == zip[i+j-1]));
        }
        
    if(F[len1][len2])
        return 1;
    else
        return 0;
}

int main()
{
    int t,i,j,k;
    char ans[2][5]={"no\n","yes\n"};
    
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        scanf("%s %s %s",in1,in2,zip);
        len1=strlen(in1);
        len2=strlen(in2);
        printf("Data set %d: %s",i,ans[ solve() ]);
        
        for(j=0;j<=len1;j++)
            for(k=0;k<=len2;k++)
                F[j][k]=false;
    }
    return 0;
}