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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2006: [NOI2010]超级钢琴  

2014-01-29 16:44:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


刚开始搞错了题意,以为每个和弦里的美妙度集合要不同。。。傻了半天终于理解了,1Y


代码:

  • #include <cstdio>
  • #include <algorithm>
  • #include <cstring>
  • #include <cmath>
  • #include <queue>
  •  
  • using namespace std ;
  •  
  • #define MAXN 500100
  • #define MAXD 24
  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
  • #define ll long long
  •  
  • int a[ MAXN ] , n , k , pre[ MAXN ] , st[ MAXN ][ MAXD ] , D , L , R ;
  • int pos[ MAXN ][ MAXD ] ;
  •  
  • int Min( int l , int r ) {
  •     int d = int( log2( r - l + 1 ) ) ;
  •     return min( st[ l ][ d ] , st[ r - ( 1 << d ) + 1 ][ d ] ) ;
  • }
  •  
  • int Pos( int l , int r ) {
  •     int d = int( log2( r - l + 1 ) ) ;
  •     if ( st[ l ][ d ] < st[ r - ( 1 << d ) + 1 ][ d ] ) {
  •         return pos[ l ][ d ] ; 
  •     } else return pos[ r - ( 1 << d ) + 1 ][ d ] ;
  • }
  •  
  • struct node {
  •     int l , r , x ;
  •     ll v ;
  •     node( int _l , int _r , int _x ) : l( _l ) , r( _r ) , x( _x ) , v( pre[ _x ] - Min( _l , _r ) ) {
  •          
  •     }
  •     bool operator < ( const node &a ) const {
  •         return v < a.v ;
  •     }
  • };
  • priority_queue < node > q ;
  •  
  • void Init(  ) {
  •     scanf( "%d%d%d%d" , &n , &k , &L , &R ) ;
  •     rep( i , n ) scanf( "%d" , &a[ i ] ) ;
  •     pre[ 0 ] = 0 ;
  •     rep( i , n ) pre[ i ] = pre[ i - 1 ] + a[ i ] ;
  •     D = int( log2( n ) ) + 1 ;
  •     for ( int i = 0 ; i <= n ; ++ i ) {
  •         st[ i ][ 0 ] = pre[ i ] , pos[ i ][ 0 ] = i ;
  •     }
  •     rep( i , D ) {
  •         for ( int j = 0 ; j <= n ; ++ j ) {
  •             if ( st[ j ][ i - 1 ] < st[ j + ( 1 << ( i - 1 ) ) ][ i - 1 ] ) {
  •                 st[ j ][ i ] = st[ j ][ i - 1 ] , pos[ j ][ i ] = pos[ j ][ i - 1 ] ;
  •             } else {
  •                 st[ j ][ i ] = st[ j + ( 1 << ( i - 1 ) ) ][ i - 1 ] ;
  •                 pos[ j ][ i ] = pos[ j + ( 1 << ( i - 1 ) ) ][ i - 1 ] ;
  •             }
  •         }
  •     }
  •     while ( ! q.empty(  ) ) q.pop(  ) ;
  •     for ( int i = 0 ; i ++ < n ; ) {
  •         int l = max( 0 , i - R ) , r = i - L ;
  •         if ( r < 0 ) continue ;
  •         q.push( node( l , r , i ) ) ;
  •     }
  • }
  •  
  • void Solve(  ) {
  •     ll ans = 0 ;
  •     while ( k -- ) {
  •         node ret = q.top(  ) ; q.pop(  ) ;
  •         ans += ret.v ;
  •         int p = Pos( ret.l , ret.r ) ;
  •         if ( ret.l < p ) q.push( node( ret.l , p - 1 , ret.x ) ) ;
  •         if ( ret.r > p ) q.push( node( p + 1 , ret.r , ret.x ) ) ;
  •     }
  •     printf( "%lld\n" , ans ) ;
  • }
  •  
  • int main(  ) {
  •     Init(  ) ;
  •     Solve(  ) ;
  •     return 0 ;
  • }



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

历史上的今天

评论

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

页脚

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