toj_2958.cpp

Tianjin University Online Judge 的80多道题目 .

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define MAXLEN 210
int n , dp[ MAXLEN ][ MAXLEN ];
int result;
const char leftB[] = "{([";
const char rightB[] = "})]";
char str[ MAXLEN ];

bool match( char a , char b )
{
    if( a == '(' && b == ')' ||  a == '[' && b == ']' || a == '{' && b == '}' )
        return true;
    else
        return false;
}

void find_dp()
{
    int i , j , k , p;
    memset( dp , 0 , sizeof( dp ) );
    for( i = 0 ; i < n; i++ )
        dp[ i ][ i - 1 ] = 1;
    for( k = 2; k < n; k++ ){
        for( i = 0; i <= n - k; i++ ){  
            j = i + k - 1;
            if( match( str[ i ] , str[ j ] ) )
                dp[ i ][ j ] = dp[ i + 1 ][ j - 1 ];
            else if ( strchr( leftB , str[ i ] ) && str[ j ] == '?' || strchr( rightB , str[ j ] ) && str[ i ] == '?' )
                dp[ i ][ j ] = dp[ i + 1 ][ j - 1 ];
            else if( str[ i ] == '?' && str[ j ] == '?' )
                dp[ i ][ j ] = 3 * dp[ i + 1 ][ j - 1 ];
            else {
                for( p = i + 1 ; p < j; p++ )
                    if( match( str[ i ] , str[ k ] ) )
                        dp[ i ][ j ] = dp[ i + 1 ][ k - 1 ] + dp[ k + 1 ][ j ];
                    else if ( strchr( leftB, str[ i ] ) && str[ k ] == '?' || strchr( rightB , str[ k ] ) && str[ i ] == '?' )
                        dp[ i ][ j ] = dp[ i + 1 ][ k - 1 ] + dp[ k + 1 ][ j ];
                    else if( str[ i ] == '?' && str[ k ] == '?' )
                        dp[ i ][ j ] = 3 * dp[ i + 1 ][ k - 1 ] + dp[ k + 1 ][ j ];
            }
        }
    }
}

int main()
{
    int i , j;
    scanf( "%d" , &n );
    scanf( "%s" , str );
    find_dp();
    for( i = 0; i < n; i++ ){
        for( j = 0; j < n; j++ )
            printf( "%d " , dp[ i ][ j ] );
        printf( "\n" );
    }
            
    printf( "%d\n" , dp[ 0 ][ n - 1 ] );
    system( "pause" );
    return 0;
}