BZOJ-1055: [HAOI2008]玩具取名（区间DP）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1055

这几天脑子不太好尽刷些傻叉的水题。。。区间DP，没什么好说的。。。除了吐槽一下自己因为没删注释性输出而WA了好几次之外额。。。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ;
 
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
 
int getchr(  ) {
    int ch ; for ( ch = getchar(  ) ; ch != 'W' && ch != 'I' && ch != 'N' && ch != 'G' ; ch = getchar(  ) ) ;
    return ch == 'W' ? 0 : ( ch == 'I' ? 1 : ( ch == 'N' ? 2 : 3 ) ) ;
}
 
void putchr( int ch ) {
    switch ( ch ) {
        case 0 : putchar( 'W' ) ; break ;
        case 1 : putchar( 'I' ) ; break ;
        case 2 : putchar( 'N' ) ; break ;
        case 3 : putchar( 'G' ) ; break ;
    }
}
 
const int maxn = 210 ;
 
bool dp[ maxn ][ maxn ][ 4 ] , flag[ maxn ][ maxn ][ 4 ] ;
int n[ 4 ] , turn[ 4 ][ maxn ][ 2 ] , len ;
char s[ maxn ] ;
 
bool dfs( int l , int r , int c ) {
    if ( flag[ l ][ r ][ c ] ) return dp[ l ][ r ][ c ] ;
    if ( l == r ) {
        dp[ l ][ r ][ c ] = ( c == 0 && s[ l ] == 'W' ) || ( c == 1 && s[ l ] == 'I' ) || ( c == 2 && s[ l ] == 'N' ) || ( c == 3 && s[ l ] == 'G' ) ;
    } else {
        rep( i , n[ c ] ) {
            for ( int j = l ; j < r ; ++ j ) {
                dp[ l ][ r ][ c ] |= ( dfs( l , j , turn[ c ][ i ][ 0 ] ) && dfs( j + 1 , r , turn[ c ][ i ][ 1 ] ) ) ;
                if ( dp[ l ][ r ][ c ] ) break ;
            }
            if ( dp[ l ][ r ][ c ] ) break ;
        }
    }
    flag[ l ][ r ][ c ] = true ;
    return dp[ l ][ r ][ c ] ;
}
 
int main(  ) {
    memset( dp , false , sizeof( dp ) ) ;
    memset( flag , false , sizeof( flag ) ) ;
    for ( int i = 0 ; i < 4 ; ++ i ) scanf( "%d" , n + i ) ;
    for ( int i = 0 ; i < 4 ; ++ i ) {
        rep( j , n[ i ] ) {
            turn[ i ][ j ][ 0 ] = getchr(  ) ;
            turn[ i ][ j ][ 1 ] = getchr(  ) ;
        }
    }
    scanf( "%s" , s + 1 ) ;
    len = strlen( s + 1 ) ;
    bool F = false ;
    for ( int i = 0 ; i < 4 ; ++ i ) if ( dfs( 1 , len , i ) ) {
        putchr( i ) ; F = true ;
    }
    if ( ! F ) printf( "The name is wrong!" ) ;
    putchar( '\n' ) ;
    return 0 ; 
}