BZOJ-1079: [SCOI2008]着色方案（DP）

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

囧囧的一道六维DP，记得用long long

代码：

#include <iostream>

#include <algorithm>

#include <cstring>

#include <queue>

#include <cstdio>

  

using namespace std ;

  

#define MOD( x ) ( x %= MAX )

#define MAX 1000000007

#define ll long long

  

bool f[ 16 ][ 16 ][ 16 ][ 16 ][ 16 ][ 16 ] ;

ll dp[ 16 ][ 16 ][ 16 ][ 16 ][ 16 ][ 16 ] , k ;

  

struct state {

    int a , b , c , d , e , x ;

    state(  ) {

        a = b = c = d = e = x = 0 ;

    }

    state( int _a , int _b , int _c , int _d , int _e , int _x ) : a( _a ) , b( _b ) , c( _c ) , d( _d ) , e( _e ) , x( _x ) {

          

    }

} ;

queue < state > Q ;

  

void Init(  ) {

    memset( f , false , sizeof( f ) ) ;

    memset( dp , 0 , sizeof( dp ) ) ;

    state S ;

    cin >> k ;

    for ( int i = 0 ; i ++ < k ; ) {

        int x ; cin >> x ;

        switch ( x ) {

            case 1 :

                S.a ++ ;

                break ;

            case 2 :

                S.b ++ ;

                break ;

            case 3 :

                S.c ++ ;

                break ;

            case 4 :

                S.d ++ ;

                break ;

            case 5 :

                S.e ++ ;

                break ;

        }

    }

    while ( ! Q.empty(  ) ) Q.pop(  ) ;

    int a = S.a , b = S.b , c = S.c , d = S.d , e = S.e , x = S.x ;

    if ( a ) {

        f[ a - 1 ][ b ][ c ][ d ][ e ][ 0 ] = true ;

        dp[ a - 1 ][ b ][ c ][ d ][ e ][ 0 ] = a ;

        Q.push( state( a - 1 , b , c , d , e , 0 ) ) ;

    }

    if ( b ) {

        f[ a + 1 ][ b - 1 ][ c ][ d ][ e ][ 1 ] = true ;

        dp[ a + 1 ][ b - 1 ][ c ][ d ][ e ][ 1 ] = b ;

        Q.push( state( a + 1 , b - 1 , c , d , e , 1 ) ) ;

    }

    if ( c ) {

        f[ a ][ b + 1 ][ c - 1 ][ d ][ e ][ 2 ] = true ;

        dp[ a ][ b + 1 ][ c - 1 ][ d ][ e ][ 2 ] = c ;

        Q.push( state( a , b + 1 , c - 1 , d , e , 2 ) ) ;

    }

    if ( d ) {

        f[ a ][ b ][ c + 1 ][ d - 1 ][ e ][ 3 ] = true ;

        dp[ a ][ b ][ c + 1 ][ d - 1 ][ e ][ 3 ] = d ;

        Q.push( state( a , b , c + 1 , d - 1 , e , 3 ) ) ;

    }

    if ( e ) {

        f[ a ][ b ][ c ][ d + 1 ][ e - 1 ][ 4 ] = true ;

        dp[ a ][ b ][ c ][ d + 1 ][ e - 1 ][ 4 ] = e ;

        Q.push( state( a , b , c , d + 1 , e - 1 , 4 ) ) ;

    }

}

  

void Update( int a , int b , int c , int d , int e , int x , ll cnt ) {

    if ( ! f[ a ][ b ][ c ][ d ][ e ][ x ] ) {

        f[ a ][ b ][ c ][ d ][ e ][ x ] = true ;

        Q.push( state( a , b , c , d , e , x ) ) ;

    }

    dp[ a ][ b ][ c ][ d ][ e ][ x ] += cnt ;

    MOD( dp[ a ][ b ][ c ][ d ][ e ][ x ] ) ;

}

  

void Solve(  ) {

    while ( ! Q.empty(  ) ) {

        state v = Q.front(  ) ; Q.pop(  ) ;

        int a = v.a , b = v.b , c = v.c , d = v.d , e = v.e , x = v.x ;

        ll temp = dp[ a ][ b ][ c ][ d ][ e ][ x ] ;

        if ( a ) {

            ll rec = a - ( x == 1 ) ;

            Update( a - 1 , b , c , d , e , 0 , temp * rec ) ;

        }

        if ( b ) {

            ll rec = b - ( x == 2 ) ;

            Update( a + 1 , b - 1 , c , d , e , 1 , temp * rec ) ;

        }

        if ( c ) {

            ll rec = c - ( x == 3 ) ;

            Update( a , b + 1 , c - 1 , d , e , 2 , temp * rec ) ;

        }

        if ( d ) {

            ll rec = d - ( x == 4 ) ;

            Update( a , b , c + 1 , d - 1 , e , 3 , temp * rec ) ;

        }

        if ( e ) {

            ll rec = e ;

            Update( a , b , c , d + 1 , e - 1 , 4 , temp * rec ) ;

        }

    }

    cout << dp[ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ] << endl ;

}

  

int main(  ) {

    Init(  ) ;

    Solve(  ) ;

    return 0 ;

}