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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1564: [NOI2009]二叉查找树(DP)  

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

  下载LOFTER 我的照片书  |

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


考虑到树的中序遍历是唯一的,那么区间dp,由于一个[n,n+1)里面的实数有无穷个可以取,所以,我们可以把权值离散化之后分成(0,1),[1,2)...[n,n+1)来表示,分别编号为0...n,然后令dp(l,r,w)表示(l,r)这个区间压成一棵子树,然后根节点的权值编号为w,然后dp之,直接做是O(n^5)应该会TLE,所以可以dp过程中弄个变量维护一下后缀最小值,那么就可以O(n^4)了。


代码:

  • #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 )

  •  

  • typedef long long ll ;

  •  

  • const int maxn = 75 ;

  •  

  • struct ntype {

  •         int d , v , u ;

  •         bool operator < ( const ntype &x ) const {

  •                 return d < x.d ;

  •         }

  • } t[ maxn ] ;

  •  

  • int a[ maxn ] , b[ maxn ] , n , m = 0 , k , w[ maxn ] , sum[ maxn ] ;

  •  

  • inline int getp( int x ) {

  •         if ( x == b[ 1 ] ) return 1 ;

  •         if ( x == b[ m ] ) return m ;

  •         int l = 1 , r = m , mid ;

  •         while ( r - l > 1 ) {

  •                 mid = ( l + r ) >> 1 ;

  •                 if ( b[ mid ] == x ) return mid ;

  •                 if ( x < b[ mid ] ) r = mid ; else l = mid ;

  •         }

  • }

  •  

  • const int inf = 1000000000 ;

  • const ll INF = ll( inf ) * ll( inf ) ;

  •  

  • ll dp[ maxn ][ maxn ][ maxn ] , suff[ 2 ][ maxn ] ;

  • bool used[ maxn ][ maxn ] ;

  •  

  • void dfs( int l , int r ) {

  •         if ( used[ l ][ r ] ) return ;

  •         used[ l ][ r ] = true ;

  •         if ( l > r ) {

  •                 REP( i , 0 , n ) dp[ l ][ r ][ i ] = 0 ; return ;

  •         }

  •         if ( l == r ) {

  •                 REP( i , 0 , n ) dp[ l ][ r ][ i ] = t[ l ].u + ( i != w[ l ] ) * k ;

  •                 return ;

  •         }

  •         REP( i , l , r ) dfs( l , i - 1 ) , dfs( i + 1 , r ) ;

  •         REP( i , 0 , n ) dp[ l ][ r ][ i ] = INF ;

  •         REP( i , l , r ) {

  •                 suff[ 0 ][ n + 1 ] = suff[ 1 ][ n + 1 ] = INF ;

  •                 DOWN( j , n , 0 ) {

  •                         suff[ 0 ][ j ] = min( suff[ 0 ][ j + 1 ] , dp[ l ][ i - 1 ][ j ] ) ;

  •                         suff[ 1 ][ j ] = min( suff[ 1 ][ j + 1 ] , dp[ i + 1 ][ r ][ j ] ) ;

  •                         dp[ l ][ r ][ j ] = min( dp[ l ][ r ][ j ] , suff[ 0 ][ j ] + suff[ 1 ][ j ] + ll( k ) * ll( j != w[ i ] ) ) ;

  •                 }

  •         }

  •         REP( i , 0 , n ) dp[ l ][ r ][ i ] += ll( sum[ r ] - sum[ l - 1 ] ) ;

  • }

  •  

  • int main(  ) {

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

  •         rep( i , n ) scanf( "%d" , &t[ i ].d ) ;

  •         rep( i , n ) {

  •                 scanf( "%d" , &t[ i ].v ) ; a[ i ] = t[ i ].v ;

  •         }

  •         rep( i , n ) scanf( "%d" , &t[ i ].u ) ;

  •         sort( a + 1 , a + n + 1 ) , sort( t + 1 , t + n + 1 ) ;

  •         rep( i , n ) if ( i == 1 || a[ i ] != a[ i - 1 ] ) b[ ++ m ] = a[ i ] ;

  •         sum[ 0 ] = 0 ;

  •         rep( i , n ) {

  •                 sum[ i ] = sum[ i - 1 ] + t[ i ].u ; w[ i ] = getp( t[ i ].v ) ;

  •         }

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

  •         dfs( 1 , n ) ;

  •         ll ans = INF ;

  •         REP( i , 0 , n ) ans = min( ans , dp[ 1 ][ n ][ i ] ) ;

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

  •         return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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