BZOJ-1564: [NOI2009]二叉查找树(DP)

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

考虑到树的中序遍历是唯一的，那么区间dp，由于一个[n,n+1)里面的实数有无穷个可以取，所以，我们可以把权值离散化之后分成(0,1),[1,2)...[n,n+1)来表示，分别编号为0...n，然后令dp(l,r,w)表示(l,r)这个区间压成一棵子树，然后根节点的权值编号为w，然后dp之，直接做是O(n^{5）应该会TLE，所以可以dp过程中弄个变量维护一下后缀最小值，那么就可以O(n}4)了。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

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

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

#define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )

 

typedef long long ll ;

 

const int maxn = 75 ;

 

struct ntype {

        int d , v , u ;

        bool operator < ( const ntype &x ) const {

                return d < x.d ;

        }

} t[ maxn ] ;

 

int a[ maxn ] , b[ maxn ] , n , m = 0 , k , w[ maxn ] , sum[ maxn ] ;

 

inline int getp( int x ) {

        if ( x == b[ 1 ] ) return 1 ;

        if ( x == b[ m ] ) return m ;

        int l = 1 , r = m , mid ;

        while ( r - l > 1 ) {

                mid = ( l + r ) >> 1 ;

                if ( b[ mid ] == x ) return mid ;

                if ( x < b[ mid ] ) r = mid ; else l = mid ;

        }

}

 

const int inf = 1000000000 ;

const ll INF = ll( inf ) * ll( inf ) ;

 

ll dp[ maxn ][ maxn ][ maxn ] , suff[ 2 ][ maxn ] ;

bool used[ maxn ][ maxn ] ;

 

void dfs( int l , int r ) {

        if ( used[ l ][ r ] ) return ;

        used[ l ][ r ] = true ;

        if ( l > r ) {

                REP( i , 0 , n ) dp[ l ][ r ][ i ] = 0 ; return ;

        }

        if ( l == r ) {

                REP( i , 0 , n ) dp[ l ][ r ][ i ] = t[ l ].u + ( i != w[ l ] ) * k ;

                return ;

        }

        REP( i , l , r ) dfs( l , i - 1 ) , dfs( i + 1 , r ) ;

        REP( i , 0 , n ) dp[ l ][ r ][ i ] = INF ;

        REP( i , l , r ) {

                suff[ 0 ][ n + 1 ] = suff[ 1 ][ n + 1 ] = INF ;

                DOWN( j , n , 0 ) {

                        suff[ 0 ][ j ] = min( suff[ 0 ][ j + 1 ] , dp[ l ][ i - 1 ][ j ] ) ;

                        suff[ 1 ][ j ] = min( suff[ 1 ][ j + 1 ] , dp[ i + 1 ][ r ][ j ] ) ;

                        dp[ l ][ r ][ j ] = min( dp[ l ][ r ][ j ] , suff[ 0 ][ j ] + suff[ 1 ][ j ] + ll( k ) * ll( j != w[ i ] ) ) ;

                }

        }

        REP( i , 0 , n ) dp[ l ][ r ][ i ] += ll( sum[ r ] - sum[ l - 1 ] ) ;

}

 

int main(  ) {

        scanf( "%d%d" , &n , &k ) ;

        rep( i , n ) scanf( "%d" , &t[ i ].d ) ;

        rep( i , n ) {

                scanf( "%d" , &t[ i ].v ) ; a[ i ] = t[ i ].v ;

        }

        rep( i , n ) scanf( "%d" , &t[ i ].u ) ;

        sort( a + 1 , a + n + 1 ) , sort( t + 1 , t + n + 1 ) ;

        rep( i , n ) if ( i == 1 || a[ i ] != a[ i - 1 ] ) b[ ++ m ] = a[ i ] ;

        sum[ 0 ] = 0 ;

        rep( i , n ) {

                sum[ i ] = sum[ i - 1 ] + t[ i ].u ; w[ i ] = getp( t[ i ].v ) ;

        }

        memset( used , false , sizeof( used ) ) ;

        dfs( 1 , n ) ;

        ll ans = INF ;

        REP( i , 0 , n ) ans = min( ans , dp[ 1 ][ n ][ i ] ) ;

        printf( "%lld\n" , ans ) ;

        return 0 ;

}