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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1055: [HAOI2008]玩具取名(区间DP)  

2014-04-07 21:37:00|  分类: oi,bzoj,DP |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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



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

历史上的今天

评论

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

页脚

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