题目：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 ;
}
网友评论