BZOJ-1563: [NOI2009]诗人小G（单调性DP）

题目：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 ;

}