POJ 2192 Zipper

aの前i文字とbの前j文字がcの前i+j文字を構成できるかどうかを判断し、プッシュし、配列が大きくなることに注意し、205がwaする.

/*Accepted 220K 0MS C++ 911B 2012-04-22 10:42:42 */



#include<cstdio>

#include<cstring>

#include<cstdlib>

#define MAXN 255



bool match[MAXN][MAXN];

char a[MAXN], b[MAXN], c[MAXN << 1];

int la, lb, lc;



void dp()

{

    int i, j;

    la = strlen( a + 1), lb = strlen( b + 1), lc = strlen( c + 1);

    if( a[la] == c[lc] || b[lb] == c[lc])

    {

        match[0][0] = true;

        for( i = 0; a[i]; ++ i)

            for( j = 0; b[j]; ++ j)

            {

                match[i][j] = i | j ? false : true;

                int k = i + j;

                if( i > 0 && a[i] == c[k])

                    match[i][j] |= match[i - 1][j];

                if( j > 0 && b[j] == c[k])

                    match[i][j] |= match[i][j - 1];

            }

    }

    else match[la][lb] = false;

}



int main()

{

    int T;

    scanf( "%d", &T);

    for( int t = 1; t <= T; t ++)

    {

        a[0] = b[0] = c[0] = '0';

        scanf( "%s%s%s", a + 1, b + 1, c + 1);

        dp();

        printf( "Data set %d: ", t);

        if( match[la][lb]) printf( "yes
");

        else printf( "no
");

    }

    return 0;

}