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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1495: [NOI2006]网络收费 (状压DP)  

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

  下载LOFTER 我的照片书  |

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


首先可以很容易的把贡献分开处理成每一个节点对LCA的贡献,然后考虑DP,我们发现每个状态如果包括叶子的状态的话太大,那么变成包括祖先的状态,然后从下往上递推,dp(i,j,k)表示节点i,包括了j个A节点,祖先状态为k(状压)的最优解,然后递推即可,这里的状态是稀疏的,我们可以数学方法算出状态数为O(2^(2n))级别,转移开销是O(n2^(2n))级别,然后用一个HASH来存即可。


代码(改了N久HASH才终于不MLE+TLE了QAQ):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <vector>

  •   

  • using namespace std ;

  •   

  • #define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )

  • #define Rep( i , x ) for ( int i = 0 ; i < x ; ++ i )

  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

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

  •   

  • typedef long long ll ;

  •   

  • const int maxs = 1015043 ;

  • const int maxn = 10 ;

  •   

  • struct node {

  •     int i , j , k , v ;

  •     node( int _i , int _j , int _k , int _v ) : i( _i ) , j( _j ) , k( _k ) , v( _v ) {

  •     }

  • } ;

  •   

  • struct HASH {

  •     vector < node > V[ maxs ] ;

  •     inline void Init(  ) {

  •         Rep( i , maxs ) V[ i ].clear(  ) ;

  •     }

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

  •         int p = ( ll ) i * 117191 % maxs + j * 311123 % maxs + k ; p %= maxs ;

  •         int s = V[ p ].size(  ) ;

  •         Rep( h , s ) if ( V[ p ][ h ].i == i && V[ p ][ h ].j == j && V[ p ][ h ].k == k ) {

  •             if ( v < V[ p ][ h ].v ) V[ p ][ h ].v = v ; return ;

  •         }

  •         V[ p ].push_back( node( i , j , k , v ) ) ;

  •     }

  •     inline int ask( int i , int j , int k ) {

  •         int p = ( ll ) i * 117191 % maxs + j * 311123 % maxs + k ; p %= maxs ;

  •         int s = V[ p ].size(  ) ;

  •         Rep( h , s ) if ( V[ p ][ h ].i == i && V[ p ][ h ].j == j && V[ p ][ h ].k == k ) {

  •             return V[ p ][ h ].v ;

  •         }

  •         return 1000000000 ;

  •     }

  • } dp[ 2 ] ;

  •   

  • int n , N , C[ 1 << maxn ] , D[ 1 << maxn ] , f[ 1 << maxn ][ 1 << maxn ] ;

  • int ht[ 1 << ( maxn + 1 ) ] , pt = 0 ;

  •   

  • int ch ;

  •   

  • inline void getint( int &t ) {

  •     for ( ch = getchar(  ) ; ch < '0' || ch > '9' ; ch = getchar(  ) ) ;

  •     t = ch - '0' ;

  •     for ( ch = getchar(  ) ; ch >= '0' && ch <= '9' ; ch = getchar(  ) ) {

  •         t = t * 10 + ch - '0' ;

  •     }

  • }

  •   

  • int g[ 2 ][ 2 ][ 1 << maxn ] ;

  •   

  • inline void getg( int x , int i ) {

  •     int a , b ;

  •     Rep( j , N ) {

  •         a = 0 , b = 0 ;

  •         for ( int k = ( N + i ) >> 1 , h = 1 ; k ; k >>= 1 , h <<= 1 ) {

  •             if ( j & h ) b += f[ i ][ k ] ; else a += f[ i ][ k ] ;

  •         }

  •         if ( C[ i ] ) a += D[ i ] ; else b += D[ i ] ;

  •         g[ x ][ 1 ][ j ] = a , g[ x ][ 0 ][ j ] = b ;

  •     }

  • }

  •   

  • int main(  ) {

  •     getint( n ) ; N = 1 << n ;

  •     Rep( i , N ) getint( C[ i ] ) ;

  •     Rep( i , N ) getint( D[ i ] ) ;

  •     int x , a , b ;

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

  •     Rep( i , N ) REP( j , ( i + 1 ) , ( N - 1 ) ) {

  •         getint( x ) ;

  •         for ( a = N + i , b = N + j ; a != b ; a >>= 1 , b >>= 1 ) ;

  •         f[ i ][ a ] += x , f[ j ][ a ] += x ;

  •     }

  •     ht[ 1 ] = 0 ;

  •     REP( i , 1 , ( N - 1 ) ) ht[ i << 1 ] = ht[ i ] + 1 , ht[ ( i << 1 ) ^ 1 ] = ht[ i ] + 1 ;

  •     int rec ;

  •     REP( i , ( N >> 1 ) , ( N - 1 ) ) {

  •         getg( 0 , ( i << 1 ) - N ) , getg( 1 , ( i << 1 ) + 1 - N ) ;

  •         int st ;

  •         REP( j , 0 , 2 ) Rep( k , ( 1 << ht[ i ] ) ) {

  •             st = ( k << 1 ) ^ ( j >= 1 ) ;

  •             REP( h , 0 , j ) {

  •                 a = h < 2 ? g[ 0 ][ h ][ st ] : 1000000000 ;

  •                 b = ( j - h ) < 2 ? g[ 1 ][ j - h ][ st ] : 1000000000 ;

  •                 dp[ pt ].add( i , j , k , a + b ) ;

  •             }

  •         }

  •     }

  •     DOWN( i , ( ( N >> 1 ) - 1 ) , 1 ) {

  •         int sz = 1 << ( n - ht[ i ] ) , fg , st ;

  •         REP( j , 0 , sz ) Rep( k , ( 1 << ht[ i ] ) ) {

  •             fg = j >= ( sz - j ) ;

  •             st = ( k << 1 ) ^ fg ;

  •             REP( h , 0 , min( j , sz >> 1 ) ) {

  •                 a = dp[ pt ].ask( i << 1 , h , st ) , b = dp[ pt ].ask( ( i << 1 ) ^ 1 , j - h , st ) ;

  •                 dp[ pt ^ 1 ].add( i , j , k , a + b ) ;

  •             }

  •         }

  •         if ( i == 1 || ht[ i ] != ht[ i - 1 ] ) {

  •             dp[ pt ].Init(  ) ; pt ^= 1 ;

  •         }

  •     }

  •     int ans = 0x7fffffff ;

  •     REP( i , 0 , N ) ans = min( ans , dp[ pt ].ask( 1 , i , 0 ) ) ;

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

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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