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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1801: [Ahoi2009]chess 中国象棋(DP)  

2014-06-11 12:00:00|  分类: oi,bzoj,DP |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


动态规划,dp(i,j,k)表示前i行有j列一个炮,k列两个炮,然后弄点组合的内容DP一下就好了。


代码(WA了N次之后改LL就A了。。。):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

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

  •  

  • typedef long long ll ;

  •  

  • const ll maxn = 110 , mod = 9999973 ;

  •  

  • ll dp[ maxn ][ maxn ][ maxn ] , n , m , ans = 0 ;

  •  

  • inline void add( ll i , ll j , ll k , ll v ) {

  •     if ( i > 0 && i <= n && j >= 0 && k >= 0 && j + k <= m ) {

  •         ( dp[ i ][ j ][ k ] += v ) %= mod ;

  •     }

  • }

  •  

  • inline ll C( ll x ) {

  •     return ( ( x * ( x - 1 ) ) / 2 ) % mod ;

  • }

  •  

  • inline ll M( ll x , ll y ) {

  •     return ( x * y ) % mod ;

  • }

  •  

  • int main(  ) {

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

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

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

  •     REP( i , 0 , ( n - 1 ) ) REP( j , 0 , m ) REP( k , 0 , m ) if ( dp[ i ][ j ][ k ] ) {

  •         ll c = dp[ i ][ j ][ k ] ;

  •         add( i + 1 , j , k , c ) ;

  •         add( i + 1 , j + 1 , k , c * ( m - j - k ) ) ;

  •         add( i + 1 , j - 1 , k + 1 , c * j ) ;

  •         add( i + 1 , j + 2 , k , c * C( m - j - k ) ) ;

  •         add( i + 1 , j - 2 , k + 2 , c * C( j ) ) ;

  •         add( i + 1 , j , k + 1 , c * M( m - j - k , j ) ) ;

  •     }

  •     REP( j , 0 , m ) REP( k , 0 , ( m - j ) ) ( ans += dp[ n ][ j ][ k ] ) %= mod ;

  •     printf( "%lld\n" , ans ) ;

  •     return 0 ;

  • }




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

历史上的今天

评论

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

页脚

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