注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-1079: [SCOI2008]着色方案(DP)  

2014-01-27 15:41:00|  分类: oi,bzoj,DP |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目: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 ;

  • }



  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018