Yuki 37 遊園地のアトラクション ( DP )

No.37 遊園地のアトラクション - yukicoder

題意：
有若干個遊樂設施，用排隊時間和娛樂程度描述。初始有 T 單位的時間，同一個設施每玩一次，娛樂程度便會減半並向下取整。求在時間內能造成的最大的娛樂值。

資料規模：
初始時間 1≤T≤10000
娛樂設施數目 1≤N≤15
排隊時間 1≤ci≤100
娛樂程度 1≤vi≤500

解法：
娛樂程度至多只會減半 10 次，之後就會變 0。因此狀態數不多，可以用動態規劃。
dp[ i ][ t ][ j ] : 已考慮前 i 個遊樂設施，時間剩 t，最後一個遊樂設施玩了 j 次，此時已有的最大可能的娛樂總值

時間 / 空間複雜度：
O( T * N * lg( max{ V } ) )

int T;
int N;
vi C;
vi V;

void init(){
  cin >> T;
  cin >> N;
  C = V = vi( N );
  for( int i = 0; i < N; ++i )
    cin >> C[ i ];
  for( int i = 0; i < N; ++i )
    cin >> V[ i ];
}

int dp[ 15 + 1 ][ 10000 + 1 ][ 10 + 1 ];

void preprocess(){
  memset( dp, -1, sizeof( dp ) );
  dp[ 0 ][ T ][ 0 ] = 0;
  for( int i = 0; i < N; ++i )
    for( int t = T; t >= 0; --t )
      for( int j = 0; j <= 10; ++j )
        if( dp[ i ][ t ][ j ] != -1 ){
          if( j + 1 <= 10 and t - C[ i ] >= 0 )
            upmax( dp[ i ][ t - C[ i ] ][ j + 1 ], dp[ i ][ t ][ j ] + ( int ) ( V[ i ] / pow( 2, j ) ) );
          upmax( dp[ i + 1 ][ t ][ 0 ], dp[ i ][ t ][ j ] );
        }
}

void solve(){
  int ans = 0;
  for( int t = 0; t <= 10000; ++t )
    for( int j = 0; j <= 10; ++j )
      upmax( ans, dp[ N ][ t ][ j ] );
  cout << ans << endl;
}