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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1492: [NOI2007]货币兑换Cash(动态规划+动态维护凸壳)  

2014-02-26 21:28:00|  分类: SBT,数据结构,dp, |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


很经典的一道把决策看成点,然后动态维护凸壳的DP题目,可以用平衡树维护,据说还可以用神奇的CDQ分治水过去(看来真的应该去学学神级分治了啊)。


代码(SBT):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • #define cal( p0 , p1 ) ( ( p0.y - p1.y ) / ( p0.x - p1.x ) )

  • #define MAXN 101000

  • #define X( x ) ( ( r[ x ] * f[ x ] ) / ( a[ x ] * r[ x ] + b[ x ] ) )

  • #define Y( x ) ( f[ x ] / ( a[ x ] * r[ x ] + b[ x ] ) )

  • #define fun( i , p ) ( a[ i ] * p.x + b[ i ] * p.y )

  • #define clear( x ) memset( x , 0 , sizeof( x ) )

  •  

  • #define update( t ) S( t ) = S( L( t ) ) + S( R( t ) ) + 1

  • #define L( t ) left[ t ]

  • #define R( t ) right[ t ]

  • #define K( t ) key[ t ]

  • #define S( t ) size[ t ]

  •  

  • const double inf = 100000000 ;

  • const double INF = inf * inf ;

  •  

  • struct itype {

  •     double x , y ;

  •     bool operator < ( const itype &a ) const {

  •         return x < a.x ;

  •     }

  •     bool operator == ( const itype &a ) const {

  •         return x == a.x ;

  •     }

  •     bool operator > ( const itype &a ) const {

  •         return x > a.x ;

  •     }

  • } key[ MAXN ] ;

  •  

  • int left[ MAXN ] , right[ MAXN ] , size[ MAXN ] , V = 0 , roof = 0 ;

  • double lk[ MAXN ] , rk[ MAXN ] ;

  •  

  • itype make( double x , double y ) {

  •     itype u ;

  •     u.x = x , u.y = y ;

  •     return u ;

  • }

  •  

  • void Left( int &t ) {

  •     int k = R( t ) ;

  •     R( t ) = L( k ) ; update( t ) ;

  •     L( k ) = t ; update( k ) ;

  •     t = k ;

  • }

  •  

  • void Right( int &t ) {

  •     int k = L( t ) ;

  •     L( t ) = R( k ) ; update( t ) ;

  •     R( k ) = t ; update( k ) ;

  •     t = k ;

  • }

  •  

  • void maintain( int &t ) {

  •     if ( S( L( L( t ) ) ) > S( R( t ) ) ) {

  •         Right( t ) ;

  •         maintain( R( t ) ) ; maintain( t ) ;

  •         return ;

  •     }

  •     if ( S( R( L( t ) ) ) > S( R( t ) ) ) {

  •         Left( L( t ) ) ; Right( t ) ;

  •         maintain( L( t ) ) , maintain( R( t ) ) ; maintain( t ) ;

  •         return ;

  •     }

  •     if ( S( R( R( t ) ) ) > S( L( t ) ) ) {

  •         Left( t ) ;

  •         maintain( L( t ) ) ; maintain( t ) ;

  •         return ;

  •     }

  •     if ( S( L( R( t ) ) ) > S( L( t ) ) ) {

  •         Right( R( t ) ) ; Left( t ) ;

  •         maintain( L( t ) ) , maintain( R( t ) ) ; maintain( t ) ;

  •         return ;

  •     }

  • }

  •  

  • void Insert( itype k , int &t ) {

  •     if ( ! t ) {

  •         t = ++ V ;

  •         S( t ) = 1 , K( t ) = k ;

  •         return ;

  •     }

  •     Insert( k , k < K( t ) ? L( t ) : R( t ) ) ;

  •     update( t ) ; maintain( t ) ;

  • }

  •  

  • void Delete( itype k , int &t ) {

  •     if ( K( t ) == k ) {

  •         if ( ! L( t ) ) {

  •             t = R( t ) ; return ;

  •         } else if ( ! R( t ) ) {

  •             t = L( t ) ; return ;

  •         } else {

  •             Right( t ) ; Delete( k , R( t ) ) ;

  •         }

  •     } else Delete( k , k < K( t ) ? L( t ) : R( t ) ) ;

  •     update( t ) ; maintain( t ) ;

  • }

  •  

  • itype Prefix( itype k , int t ) {

  •     if ( ! t ) return make( - INF , - INF ) ;

  •     if ( k > K( t ) ) return max( K( t ) , Prefix( k , R( t ) ) ) ;

  •     return Prefix( k , L( t ) ) ;

  • }

  •  

  • itype Suffix( itype k , int t ) {

  •     if ( ! t ) return make( INF , INF ) ;

  •     if ( K( t ) > k ) return min( K( t ) , Suffix( k , L( t ) ) ) ;

  •     return Suffix( k , R( t ) ) ;

  • }

  •  

  • int Find( itype k , int t ) {

  •     if ( ! t ) return 0 ;

  •     if ( k == K( t ) ) return t ;

  •     return Find( k , k < K( t ) ? L( t ) : R( t ) ) ;

  • }

  •  

  • void Push( itype k ) {

  •     int t = Find( k , roof ) ;

  •     if ( t ) {

  •         if ( K( t ).y >= k.y ) return ;

  •         Delete( K( t ) , roof ) ;

  •     }

  •     itype pre = Prefix( k , roof ) , suff = Suffix( k , roof ) ;

  •     if ( cal( pre , k ) > cal( pre , suff ) ) {

  •         for ( ; pre.y != - INF ; ) {

  •             itype ret = Prefix( pre , roof ) ;

  •             if ( cal( ret , pre ) <= cal( pre , k ) ) {

  •                 Delete( pre , roof ) ;

  •                 pre = ret ;

  •             } else break ;

  •         }

  •         for ( ; suff.y != - INF ; ) {

  •             itype ret = Suffix( suff , roof ) ;

  •             if ( cal( k , ret ) >= cal( k , suff ) ) {

  •                 Delete( suff , roof ) ;

  •                 suff = ret ;

  •             } else break ;

  •         }

  •         Insert( k , roof ) ;

  •         lk[ V ] = cal( pre , k ) , rk[ V ] = cal( k , suff ) ;

  •         rk[ Find( pre , roof ) ] = cal( pre , k ) ;

  •         lk[ Find( suff , roof ) ] = cal( k , suff ) ;

  •     }

  • }

  •  

  • itype Select( double k , int t ) {

  •     if ( K( t ).x == - inf ) return Select( k , R( t ) ) ;

  •     if ( K( t ).x == inf ) return Select( k , L( t ) ) ;

  •     if ( lk[ t ] >= k && k >= rk[ t ] ) return K( t ) ;

  •     if ( rk[ t ] > k ) return Select( k , R( t ) ) ;

  •     if ( lk[ t ] < k ) return Select( k , L( t ) ) ;

  • }

  •  

  • double a[ MAXN ] , b[ MAXN ] , r[ MAXN ] , f[ MAXN ] , money ;

  • int n ;

  •  

  • int main(  ) {

  •     clear( left ) , clear( right ) , clear( size ) ;

  •     Insert( make( 0 , - INF ) , roof ) , Insert( make( inf , - INF ) , roof ) ;

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

  •     for ( int i = 0 ; i ++ < n ; ) scanf( "%lf%lf%lf" , a + i , b + i , r + i ) ;

  •     for ( int i = 0 ; i ++ < n ; ) {

  •         f[ i ] = max( money , f[ i - 1 ] ) ;

  •         if ( i > 1 ) {

  •             itype p = Select( - a[ i ] / b[ i ] , roof ) ;

  •             f[ i ] = max( f[ i ] , fun( i , p ) ) ;

  •         }

  •         Push( make( X( i ) , Y( i ) ) ) ;

  •     }

  •     printf( "%.3f\n" , f[ n ] ) ;

  •     return 0 ;

  • }


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

历史上的今天

评论

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

页脚

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