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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2726: [SDOI2012]任务安排(DP+平衡树维护凸壳)  

2014-03-28 20:14:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


动态转移方程:f(j)=min{f(j)+【sumt(i)-sumt(j)+S】*sumf(i)}

sum(i)表示从i到n的和。

然后这个方程就可以用一个平衡树来维护一个决策的下凸壳,然后就做到O(n log n),然后就可以A了。


代码(可怜我的treap居然比set还慢 555):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cstdlib>

  •  

  • using namespace std ;

  •  

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

  • #define down( i , x ) for ( int i = x ; i ; -- i )

  •  

  • #define L( t ) left[ t ]

  • #define R( t ) right[ t ]

  • #define pre( t ) prefix[ t ]

  • #define suff( t ) suffix[ t ]

  • #define P( t ) priority[ t ]

  • #define K( t ) key[ t ]

  •  

  • const int maxn = 300100 ;

  •  

  • typedef long long ll ;

  • typedef long double ld ;

  •  

  • ll inf = 1000000000 ;

  • ll INF = inf * inf ;

  •  

  • struct point {

  •      

  •     ld x , y ;

  •     int pos ;

  •      

  •     void oper( ld _x , ld _y , int _pos ) {

  •         x = _x , y = _y , pos = _pos ;

  •     }

  •      

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

  •         return x < a.x ;

  •     }

  •      

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

  •         return x == a.x ;

  •     }

  •      

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

  •         return x > a.x ;

  •     }

  •      

  •     ld cal( point rec ) {

  •         return ( y - rec.y ) / ( x - rec.x ) ;

  •     }

  •      

  • } key[ maxn ] ;

  •  

  • int left[ maxn ] , right[ maxn ] , prefix[ maxn ] , suffix[ maxn ] , priority[ maxn ] ;

  • int V , roof ;

  •  

  • void Left( int &t ) {

  •     int k = R( t ) ;

  •     R( t ) = L( k ) ;

  •     L( k ) = t ;

  •     t = k ;

  • }

  •  

  • void Right( int &t ) {

  •     int k = L( t ) ;

  •     L( t ) = R( k ) ;

  •     R( k ) = t ;

  •     t = k ;

  • }

  •  

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

  •     if ( ! t ) {

  •         t = ++ V ;

  •         K( t ) = k , L( t ) = R( t ) = 0 , P( t ) = rand(  ) ;

  •         return ;

  •     }

  •     if ( k < K( t ) ) {

  •         Insert( k , L( t ) ) ;

  •         if ( P( L( t ) ) > P( t ) ) Right( t ) ;

  •     } else {

  •         Insert( k , R( t ) ) ;

  •         if ( P( R( t ) ) > P( t ) ) Left( t ) ;

  •     }

  • }

  •  

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

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

  •         if ( ! L( t ) ) {

  •             t = R( t ) ; return ;

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

  •             t = L( t ) ; return ;

  •         } else {

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

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

  •             } else {

  •                 Left( t ) ; Delete( k , L( t ) ) ;

  •             }

  •         }

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

  • }

  •  

  • int Prefix( point k ) {

  •     int temp = 0 ;

  •     for ( int t = roof ; t ; t = k < K( t ) ? L( t ) : R( t ) ) {

  •         if ( k > K( t ) && ( ! temp || K( t ) > K( temp ) ) ) temp = t ;

  •     }

  •     return temp ;

  • }

  •  

  • int Suffix( point k ) {

  •     int temp = 0 ;

  •     for ( int t = roof ; t ; t = k < K( t ) ? L( t ) : R( t ) ) {

  •         if ( k < K( t ) && ( ! temp || K( t ) < K( temp ) ) ) temp = t ;

  •     }

  •     return temp ;

  • }

  •  

  • int Find( point k ) {

  •     for ( int t = roof ; t ; t = k < K( t ) ? L( t ) : R( t ) ) {

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

  •     }

  •     return 0 ;

  • }

  •  

  • void Push( point k ) {

  •     int rec = Find( k ) ;

  •     if ( rec ) {

  •         if ( K( rec ).y <= k.y ) return ;

  •         Delete( K( rec ) , roof ) ;

  •     }

  •     int p = Prefix( k ) , s = Suffix( k ) ;

  •     if ( k.cal( K( p ) ) >= K( p ).cal( K( s ) ) ) return ;

  •     int ret ;

  •     for ( ; K( p ).x > - inf ; ) {

  •         ret = pre( p ) ;

  •         if ( k.cal( K( ret ) ) <= K( ret ).cal( K( p ) ) ) {

  •             Delete( K( p ) , roof ) ;

  •             p = ret ;

  •         } else break ;

  •     }

  •     for ( ; K( s ).x < inf ; ) {

  •         ret = suff( s ) ;

  •         if ( k.cal( K( s ) ) >= k.cal( K( ret ) ) ) {

  •             Delete( K( s ) , roof ) ;

  •             s = ret ;

  •         } else break ;

  •     }

  •     Insert( k , roof ) ;

  •     suff( p ) = V , pre( s ) = V , pre( V ) = p , suff( V ) = s ;

  • }

  •  

  • point Search( ld k , int t ) {

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

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

  •     ld lk = K( t ).cal( K( pre( t ) ) ) , rk = K( t ).cal( K( suff( t ) ) ) ;

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

  •     if ( k < lk ) return Search( k , L( t ) ) ;

  •     if ( k > rk ) return Search( k , R( t ) ) ;

  • }

  •  

  • ll f[ maxn ] , n , S , T[ maxn ] , F[ maxn ] , sumt[ maxn ] , sumf[ maxn ] ;

  •  

  • void Init_treap(  ) {

  •     V = 2 , roof = 1 ;

  •     P( 1 ) = rand(  ) , P( 2 ) = rand(  ) ;

  •     K( 1 ).oper( ld( - inf ) , ld( INF ) , - 1 ) , K( 2 ).oper( ld( inf ) , ld( INF ) , - 1 ) ;

  •     pre( 1 ) = suff( 2 ) = 0 , suff( 1 ) = 2 , pre( 2 ) = 1 ;

  •     L( 1 ) = R( 1 ) = L( 2 ) = R( 2 ) = 0 ;

  •     if ( P( 1 ) > P( 2 ) ) {

  •         R( 1 ) = 2 ;

  •         roof = 1 ;

  •     } else {

  •         L( 2 ) = 1 ;

  •         roof = 2 ;

  •     }

  • }

  •  

  • point make( int x ) {

  •     point temp ;

  •     temp.oper( ld( sumt[ x ] ) , ld( f[ x ] ) , x ) ;

  •     return temp ;

  • }

  •  

  • int main(  ) {

  •     srand( 1221 ) ;

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

  •     rep( i , n ) scanf( "%lld%lld" , T + i , F + i ) ;

  •     sumt[ n + 1 ] = sumf[ n + 1 ] = 0 ;

  •     down( i , n ) {

  •         sumt[ i ] = sumt[ i + 1 ] + T[ i ] ;

  •         sumf[ i ] = sumf[ i + 1 ] + F[ i ] ;

  •     }

  •     Init_treap(  ) ;

  •     f[ n + 1 ] = 0 ;

  •     Push( make( n + 1 ) ) ;

  •     down( i , n ) {

  •         point rec = Search( ld( sumf[ i ] ) , roof ) ;

  •         f[ i ] = f[ rec.pos ] + ( sumt[ i ] - sumt[ rec.pos ] + S ) * sumf[ i ] ;

  •         Push( make( i ) ) ;

  •     }

  •     printf( "%lld\n" , f[ 1 ] ) ;

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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