DPトレーニングcdoj 1354柱爺忙しい[状圧DP]
私がCDOJをしないとしたら?
作業(work.pas/cpp/c)
【題名説明】Nつのことがあり、それぞれに2つの属性a,bがあります.今、あなたはある順序でこのNつのことをしなければなりません.この人が今やっていることを考えると、iです.彼がやった前のことはjです.では、彼がやった代価は(a[i]|a[j])-(a[i]&a[j])です.前に仕事がなければ、代価はa[i]ですが、物事には軽重緩急の区別があります.本来の順序でのことiは、最大で任意のことをやり終えた直後のことj,ii+b[i]は、事iの前にはできない.【入力形式】入力の最初の行は整数Nであり、N件のことをすることを表す.次のN行は、a[i]とb[i]の2つの数を表す.【出力フォーマット】最小可能な最大転送時間を示す整数を出力【サンプル入力】2 5 1 4 0【サンプル出力】5【データ範囲】20%のデータ保証:1<=N<=15.100%のデータ保証:1<=N,a[i]<=1000,1<=b[i]<=7.
考える
dp(i,j,k)は前i件のことを考慮し,同時にiに最も近いj件の状態を考慮し,kは最近のすること距離iの距離を表す.毎回決定は2種類しかなく、先に間にしていなかった何かvを取り出してやった、すなわちdp[i][j|(1<
作業(work.pas/cpp/c)
【題名説明】Nつのことがあり、それぞれに2つの属性a,bがあります.今、あなたはある順序でこのNつのことをしなければなりません.この人が今やっていることを考えると、iです.彼がやった前のことはjです.では、彼がやった代価は(a[i]|a[j])-(a[i]&a[j])です.前に仕事がなければ、代価はa[i]ですが、物事には軽重緩急の区別があります.本来の順序でのことiは、最大で任意のことをやり終えた直後のことj,i
考える
dp(i,j,k)は前i件のことを考慮し,同時にiに最も近いj件の状態を考慮し,kは最近のすること距離iの距離を表す.毎回決定は2種類しかなく、先に間にしていなかった何かvを取り出してやった、すなわちdp[i][j|(1<
#include
using namespace std;
const int maxn = 1e3 + 25;
const int inf = 0x7f7f7f7f ;
int a[maxn] , b[maxn] , N , dp[maxn][1 << 8][20] ;
vector < int > sa;
inline void update( int & x , int v ){ x = min( x , v ); }
inline int cal ( int x , int y ){ return (x | y) - (x & y); }
inline int get ( int x , int y ){ return x >> y & 1 ;}
void Init(){
memset( dp , 0x7f , sizeof( dp ) );
}
int main(int argc,char *argv[]){
scanf("%d",&N);
for(int i = 1 ; i <= N ; ++ i) scanf("%d%d" , a + i , b + i);
Init();
dp[0][ ( 1 << 8 ) - 1][19] = 0;
for(int i = 0 ; i <= N ; ++ i)
for(int j = 0 ; j < (1 << 8) ; ++ j)
for(int k = 0 ; k < 20 ; ++ k)
if( dp[i][j][k] != inf ){
int ed = min( i , 8 ) , limit = inf;
for( int v = ed - 1 ; v >= 0 ; -- v) if( (( j >> v) & 1) == 0 ) limit = min( limit , i - v + b[ i - v ] );
if( get( j , 7 ) == 1 ) update( dp[ i + 1 ][ (j^(1<<7))<<1 ][ min( k + 1 , 19 ) ] , dp[i][j][k] );
for( int v = ed - 1 ; v >= 0 && i - v <= limit ; -- v) if( (j >> v & 1) == 0 ) update( dp[i][j | (1 << v)][v] , dp[i][j][k] + ( (k == 19) ? a[ i - v ] : cal( a[ i - v ] , a[ i - k ] ) ) );
}
int ans = inf;
for(int i = 0 ; i < 20 ; ++ i) ans = min( ans , dp[N][(1<<8)-1][i] );
printf("%d
" , ans );
return 0;
}