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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1563: [NOI2009]诗人小G(单调性DP)  

2014-06-10 13:48:00|  分类: oi,bzoj,dp,二分 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


打了个表发现决策具有单调性,然后就二分+队列维护即可,O(n log n)。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cmath>

  •  

  • using namespace std ;

  •  

  • #define sum( l , r ) ld( pre[ r ] - pre[ l - 1 ] )

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

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

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

  •  

  • typedef long long ll ;

  • typedef long double ld ;

  •  

  • const int maxn = 101000 , inf = 0x7fffffff ;

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

  • const int maxl = 50 ;

  • const ld MAX = ld( 1000000000000000000 ) ;

  •  

  • int T , N , P , L , pre[ maxn ] , len[ maxn ] ;

  • char s[ maxl ] ;

  •  

  • ld power( ld x , int cnt ) {

  •     ld y = 1 ;

  •     for ( ; cnt ; cnt >>= 1 ) {

  •         if ( cnt & 1 ) y *= x ;

  •         x *= x ;

  •     }

  •     return y ;

  • }

  •  

  • ld dp[ maxn ] ;

  •  

  • ld cost( int l , int r ) {

  •     return dp[ l - 1 ] + power( ld( abs( sum( l , r ) + ld( r - l ) - L ) ) , P ) ;

  • }

  •  

  • int q[ maxn ][ 3 ] , head = 1 , tail = 1 ;

  •  

  • int main(  ) {

  •     scanf( "%d" , &T ) ;

  •     while ( T -- ) {

  •         scanf( "%d%d%d" , &N , &L , &P ) ;

  •         pre[ 0 ] = dp[ 0 ] = 0 ;

  •         rep( i , N ) {

  •             scanf( "%s" , s ) ;

  •             pre[ i ] = pre[ i - 1 ] + ( len[ i ] = strlen( s ) ) ;

  •         }

  •         memset( q , 0 , sizeof( q ) ) ;

  •         head = tail = 1 ;

  •         q[ 1 ][ 0 ] = 1 , q[ 1 ][ 1 ] = 1 , q[ 1 ][ 2 ] = N ;

  •         rep( i , N ) {

  •             for ( ; q[ head ][ 2 ] < i ; ++ head ) ;

  •             dp[ i ] = cost( q[ head ][ 0 ] , i ) ;

  •             for ( ; head <= tail ; ) {

  •                 if ( cost( q[ tail ][ 0 ] , q[ tail ][ 1 ] ) >= cost( i + 1 , q[ tail ][ 1 ] ) ) -- tail ;

  •                 else if ( cost( q[ tail ][ 0 ] , q[ tail ][ 2 ] ) < cost( i + 1 , q[ tail ][ 2 ] ) ) break ;

  •                 else {

  •                     int l = q[ tail ][ 1 ] , r = q[ tail ][ 2 ] , mid ;

  •                     while ( r - l > 1 ) {

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

  •                         if ( cost( q[ tail ][ 0 ] , mid ) < cost( i + 1 , mid ) ) l = mid ; else r = mid ;

  •                     }

  •                     q[ tail ][ 2 ] = l ; break ;

  •                 }

  •             }

  •             if ( q[ tail ][ 2 ] < N ) {

  •                 q[ ++ tail ][ 0 ] = i + 1 ;

  •                 q[ tail ][ 1 ] = q[ tail - 1 ][ 2 ] + 1 , q[ tail ][ 2 ] = N ;

  •             }

  •         }

  •         if ( dp[ N ] > MAX ) printf( "Too hard to arrange\n" ) ; else printf( "%lld\n" , ll( dp[ N ] ) ) ;

  •         printf( "--------------------\n" ) ;

  •     }

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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