题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1495
首先可以很容易的把贡献分开处理成每一个节点对LCA的贡献，然后考虑DP，我们发现每个状态如果包括叶子的状态的话太大，那么变成包括祖先的状态，然后从下往上递推，dp(i,j,k)表示节点i，包括了j个A节点，祖先状态为k（状压）的最优解，然后递推即可，这里的状态是稀疏的，我们可以数学方法算出状态数为O(2(2n))级别，转移开销是O(n2(2n))级别，然后用一个HASH来存即可。
代码（改了N久HASH才终于不MLE+TLE了QAQ）：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std ;
#define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )
#define Rep( i , x ) for ( int i = 0 ; i < x ; ++ i )
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )
typedef long long ll ;
const int maxs = 1015043 ;
const int maxn = 10 ;
struct node {
int i , j , k , v ;
node( int _i , int _j , int _k , int _v ) : i( _i ) , j( _j ) , k( _k ) , v( _v ) {
}
} ;
struct HASH {
vector < node > V[ maxs ] ;
inline void Init( ) {
Rep( i , maxs ) V[ i ].clear( ) ;
}
inline void add( int i , int j , int k , int v ) {
int p = ( ll ) i * 117191 % maxs + j * 311123 % maxs + k ; p %= maxs ;
int s = V[ p ].size( ) ;
Rep( h , s ) if ( V[ p ][ h ].i == i && V[ p ][ h ].j == j && V[ p ][ h ].k == k ) {
if ( v < V[ p ][ h ].v ) V[ p ][ h ].v = v ; return ;
}
V[ p ].push_back( node( i , j , k , v ) ) ;
}
inline int ask( int i , int j , int k ) {
int p = ( ll ) i * 117191 % maxs + j * 311123 % maxs + k ; p %= maxs ;
int s = V[ p ].size( ) ;
Rep( h , s ) if ( V[ p ][ h ].i == i && V[ p ][ h ].j == j && V[ p ][ h ].k == k ) {
return V[ p ][ h ].v ;
}
return 1000000000 ;
}
} dp[ 2 ] ;
int n , N , C[ 1 << maxn ] , D[ 1 << maxn ] , f[ 1 << maxn ][ 1 << maxn ] ;
int ht[ 1 << ( maxn + 1 ) ] , pt = 0 ;
int ch ;
inline void getint( int &t ) {
for ( ch = getchar( ) ; ch < '0' || ch > '9' ; ch = getchar( ) ) ;
t = ch - '0' ;
for ( ch = getchar( ) ; ch >= '0' && ch <= '9' ; ch = getchar( ) ) {
t = t * 10 + ch - '0' ;
}
}
int g[ 2 ][ 2 ][ 1 << maxn ] ;
inline void getg( int x , int i ) {
int a , b ;
Rep( j , N ) {
a = 0 , b = 0 ;
for ( int k = ( N + i ) >> 1 , h = 1 ; k ; k >>= 1 , h <<= 1 ) {
if ( j & h ) b += f[ i ][ k ] ; else a += f[ i ][ k ] ;
}
if ( C[ i ] ) a += D[ i ] ; else b += D[ i ] ;
g[ x ][ 1 ][ j ] = a , g[ x ][ 0 ][ j ] = b ;
}
}
int main( ) {
getint( n ) ; N = 1 << n ;
Rep( i , N ) getint( C[ i ] ) ;
Rep( i , N ) getint( D[ i ] ) ;
int x , a , b ;
memset( f , 0 , sizeof( f ) ) ;
Rep( i , N ) REP( j , ( i + 1 ) , ( N - 1 ) ) {
getint( x ) ;
for ( a = N + i , b = N + j ; a != b ; a >>= 1 , b >>= 1 ) ;
f[ i ][ a ] += x , f[ j ][ a ] += x ;
}
ht[ 1 ] = 0 ;
REP( i , 1 , ( N - 1 ) ) ht[ i << 1 ] = ht[ i ] + 1 , ht[ ( i << 1 ) ^ 1 ] = ht[ i ] + 1 ;
int rec ;
REP( i , ( N >> 1 ) , ( N - 1 ) ) {
getg( 0 , ( i << 1 ) - N ) , getg( 1 , ( i << 1 ) + 1 - N ) ;
int st ;
REP( j , 0 , 2 ) Rep( k , ( 1 << ht[ i ] ) ) {
st = ( k << 1 ) ^ ( j >= 1 ) ;
REP( h , 0 , j ) {
a = h < 2 ? g[ 0 ][ h ][ st ] : 1000000000 ;
b = ( j - h ) < 2 ? g[ 1 ][ j - h ][ st ] : 1000000000 ;
dp[ pt ].add( i , j , k , a + b ) ;
}
}
}
DOWN( i , ( ( N >> 1 ) - 1 ) , 1 ) {
int sz = 1 << ( n - ht[ i ] ) , fg , st ;
REP( j , 0 , sz ) Rep( k , ( 1 << ht[ i ] ) ) {
fg = j >= ( sz - j ) ;
st = ( k << 1 ) ^ fg ;
REP( h , 0 , min( j , sz >> 1 ) ) {
a = dp[ pt ].ask( i << 1 , h , st ) , b = dp[ pt ].ask( ( i << 1 ) ^ 1 , j - h , st ) ;
dp[ pt ^ 1 ].add( i , j , k , a + b ) ;
}
}
if ( i == 1 || ht[ i ] != ht[ i - 1 ] ) {
dp[ pt ].Init( ) ; pt ^= 1 ;
}
}
int ans = 0x7fffffff ;
REP( i , 0 , N ) ans = min( ans , dp[ pt ].ask( 1 , i , 0 ) ) ;
printf( "%d\n" , ans ) ;
return 0 ;
}
网友评论