Yuki 37 遊園地のアトラクション ( DP )
題意:
有若干個遊樂設施,用排隊時間和娛樂程度描述。初始有 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; }