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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1065: [NOI2008]奥运物流(树形DP)  

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

  下载LOFTER 我的照片书  |

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


这个图就是一个环套了一些树。

我们可以发现每个点对答案的贡献是(Ci k^d )/(1-k^len) len表示环的长度,然后这样的话我们某一个点修改一定是改到1下面去,那么考虑环上修改的点会让环长度改变,那么枚举这些点中离1最远的那个,然后断开环,弄成一棵内向树,然后在内向树上DP,状态dp(a,b,c)表示子树a,深度b,修改了c次的最大值,然后转移就分b=1&&dep(a)!=1(修改了a)和不修改a讨论即可,这样做的复杂度就是O(n^5),常数比较小,所以可以AC。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

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

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

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

  •  

  • const int maxn = 65 ;

  •   

  • inline void update( double &x , double y ) {

  •         if ( y > x ) x = y ;

  • }

  •  

  • double k , c[ maxn ] , mul[ maxn ] , ans ;

  • int n , next[ maxn ] , m ;

  • bool flag[ maxn ] ;

  •  

  • struct edge {

  •         edge *next ;

  •         int t ;

  • } E[ maxn ] ;

  •  

  • edge *pt , *head[ maxn ] ;

  •  

  • inline void Init_edge(  ) {

  •         memset( head , 0 , sizeof( head ) ) , pt = E ;

  • }

  •  

  • inline void addedge( int s , int t ) {

  •         pt -> t = t , pt -> next = head[ s ] ; head[ s ] = pt ++ ;

  • }

  •  

  • #define travel( x ) for ( edge *p = head[ x ] ; p ; p = p -> next )

  •  

  • double dp[ maxn ][ maxn ][ maxn ] ;

  • int sz[ maxn ] , ht[ maxn ] ;

  •  

  • void geth( int now ) {

  •         sz[ now ] = 1 ;

  •         travel( now ) {

  •                 ht[ p -> t ] = ht[ now ] + 1 ;

  •                 geth( p -> t ) ;

  •                 sz[ now ] += sz[ p -> t ] ;

  •         }

  • }

  •  

  • const double inf = double( 100000000 ) * double( 100000000 ) ;

  •  

  • double g[ maxn ][ maxn ] ;

  •  

  • void dfs( int now ) {

  •         REP( i , 0 , n ) REP( j , 0 , n ) dp[ now ][ i ][ j ] = - inf ;

  •         if ( ! head[ now ] ) {

  •                 REP( i , 2 , ht[ now ] ) dp[ now ][ i ][ 0 ] = c[ now ] * mul[ i ] ;

  •                 if ( ht[ now ] != 1 ) dp[ now ][ 1 ][ 1 ] = c[ now ] * k ; else dp[ now ][ 1 ][ 0 ] = c[ now ] * k ;

  •                 return ;

  •         }

  •         travel( now ) dfs( p -> t ) ;

  •         REP( dep , 0 , ht[ now ] ) {

  •                 if ( ! dep && now != 1 ) continue ;

  •                 int cnt = 0 ;

  •                 double cost ;

  •                 REP( i , 0 , sz[ now ] ) g[ 0 ][ i ] = - inf ; g[ 0 ][ 0 ] = 0 ;

  •                 travel( now ) {

  •                         ++ cnt ;

  •                         REP( i , 0 , sz[ now ] ) g[ cnt ][ i ] = - inf ;

  •                         REP( i , 0 , sz[ p -> t ] ) {

  •                                 cost = max( dp[ p -> t ][ dep + 1 ][ i ] , dp[ p -> t ][ 1 ][ i ] ) ;

  •                                 REP( j , i , sz[ now ] ) {

  •                                         update( g[ cnt ][ j ] , g[ cnt - 1 ][ j - i ] + cost ) ;

  •                                 }

  •                         }

  •                 }

  •                 REP( tmp , 0 , sz[ now ] ) {

  •                         if ( dep == 1 && ht[ now ] != 1 ) {

  •                                 if ( tmp ) dp[ now ][ dep ][ tmp ] = g[ cnt ][ tmp - 1 ] + c[ now ] * mul[ dep ] ;

  •                         } else {

  •                                 dp[ now ][ dep ][ tmp ] = g[ cnt ][ tmp ] + c[ now ] * mul[ dep ] ;

  •                         }

  •                 }

  •         }

  • }

  •  

  • inline double solve(  ) {

  •         int len = 0 ; for ( int i = 1 ; ; i = next[ i ] ) {

  •                 ++ len ; if ( next[ i ] == 1 ) break ;

  •         }

  •         Init_edge(  ) ;

  •         REP( i , 2 , n ) addedge( next[ i ] , i ) ;

  •         ht[ 1 ] = 0 ; geth( 1 ) ;

  •         dfs( 1 ) ;

  •         double tmp = - inf ;

  •         REP( i , 0 , m ) update( tmp , dp[ 1 ][ 0 ][ i ] ) ;

  •         return tmp / ( 1.0 - mul[ len ] ) ;

  • }

  •  

  • int main(  ) {

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

  •         rep( i , n ) scanf( "%d" , next + i ) ; rep( i , n ) scanf( "%lf" , c + i ) ;

  •         mul[ 0 ] = 1 ; rep( i , n ) mul[ i ] = mul[ i - 1 ] * k ;

  •         ans = solve(  ) ;

  •         memset( flag , false , sizeof( flag ) ) ;

  •         for ( int i = 1 ; ; i = next[ i ] ) {

  •                 flag[ i ] = true ;

  •                 if ( next[ i ] == 1 ) break ;

  •         }

  •         if ( m ) {

  •                 -- m ;

  •                 rep( i , n ) if ( flag[ i ] && i != 1 && next[ i ] != 1 ) {

  •                         int t = next[ i ] ; next[ i ] = 1 ;

  •                         update( ans , solve(  ) ) ;

  •                         next[ i ] = t ;

  •                 }

  •         }

  •         printf( "%.2f\n" , ans ) ;

  •         return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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