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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1566: [NOI2009]管道取珠(DP)  

2014-07-08 13:15:00|  分类: oi,bzoj,DP |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


事实上求sigma(ai^2)可以理解成求操作序列A与操作序列B产生的结果一样的(A,B)的对数,那么DP,令dp[i][][k][h]表示A上面取了i个,下面取了j个,B上面取了k个,下面取了h个的方案数,然后DP,然后h这一维可以压掉。


代码:

  • #include <cstdio>

  •  

  • #define rep( i , l , r ) for ( int i = l ; i <= r ; ++ i )

  • #define update( x , y ) ( x += y ) %= mod ;

  •  

  • const int mod = 1024523 , maxn = 510 ;

  •  

  • int dp[ maxn ][ maxn ][ maxn ] , n , m ;

  • char s[ 2 ][ maxn ] ;

  •  

  • int main(  ) {

  •         scanf( "%d%d" , &n , &m ) ;

  •         scanf( "%s%s" , s[ 0 ] + 1 , s[ 1 ] + 1 ) ;

  •         rep( i , 0 , n ) rep( j , 0 , m ) rep( k , 0 , n ) dp[ i ][ j ][ k ] = 0 ;

  •         dp[ 0 ][ 0 ][ 0 ]= 1 ;

  •         rep( i , 0 , n ) rep( j , 0 , m ) rep( k , 0 , n ) if ( dp[ i ][ j ][ k ] ) {

  •                 if ( s[ 0 ][ i + 1 ] == s[ 0 ][ k + 1 ] ) update( dp[ i + 1 ][ j ][ k + 1 ] , dp[ i ][ j ][ k ] ) ;

  •                 if ( s[ 0 ][ i + 1 ] == s[ 1 ][ i + j - k + 1 ] ) update( dp[ i + 1 ][ j ][ k ] , dp[ i ][ j ][ k ] ) ;

  •                 if ( s[ 1 ][ j + 1 ] == s[ 0 ][ k + 1 ] ) update( dp[ i ][ j + 1 ][ k + 1 ] , dp[ i ][ j ][ k ] ) ;

  •                 if ( s[ 1 ][ j + 1 ] == s[ 1 ][ i + j - k + 1 ] ) update( dp[ i ][ j + 1 ][ k ] , dp[ i ][ j ][ k ] ) ;

  •         }

  •         printf( "%d\n" , dp[ n ][ m ][ n ] ) ;

  •         return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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