CFR 148 E. Porcelain ( DP, Knapsack )
題意:
有 N 個雙向佇列,可以從左端或右端拿東西,東西用價值描述。求總共拿 M 個東西時,最大可能價值。
資料規模:
The first line of input data contains two integers n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ 10000). The next n lines contain the values of the items on the shelves: the first number gives the number of items on this shelf (an integer between 1 and 100, inclusive), followed by the values of the items (integers between 1 and 100, inclusive), in the order in which they appear on the shelf (the first number corresponds to the leftmost item, the last one — to the rightmost one). The total number of items is guaranteed to be at least m.
TL: 1000 ms
ML: 256 MB
解法:
對 N 個雙向佇列分別預處理拿 x 個時,最大可以得到多少。之後進行 dp:
dp[ i ][ j ]:已考慮前 i 個雙向佇列,總共已拿 j 個東西,此時最大值。
時間 / 空間複雜度:
O( N * len( shelf )^2 + N * M )
int N, M; vvi book; void init(){ cin >> N >> M; book = vvi( N ); for( int i = 0; i < N; ++i ){ int size; cin >> size; book[ i ] = vi( size ); for( int j = 0; j < size; ++j ){ cin >> book[ i ][ j ]; } } } vvi wei2val; void preprocess(){ wei2val = vvi( N ); for( int i = 0; i < N; ++i ){ vvi dp( book[ i ].size() + 1, vi( book[ i ].size() + 1, -INF ) ); dp[ 0 ][ book[ i ].size() ] = 0; for( int len = book[ i ].size(); len - 1 >= 0; --len ){ for( int j = 0; j + len <= book[ i ].size(); ++j ){ upmax( dp[ j ][ j + len - 1 ], dp[ j ][ j + len ] + book[ i ][ j + len - 1 ] ); upmax( dp[ j + 1 ][ j + len ], dp[ j ][ j + len ] + book[ i ][ j ] ); } } wei2val[ i ] = vi( book[ i ].size() + 1 ); for( int j = 0; j < book[ i ].size(); ++j ){ for( int k = j; k <= book[ i ].size(); ++k ){ upmax( wei2val[ i ][ book[ i ].size() - ( k - j ) ], dp[ j ][ k ] ); } } } } vvi dp; void solve(){ dp = vvi( N + 1, vi( M + 1, -INF ) ); dp[ 0 ][ 0 ] = 0; for( int i = 0; i < N; ++i ){ for( int j = 0; j <= M; ++j ){ for( int k = 0; k <= book[ i ].size() and j + k <= M; ++k ){ upmax( dp[ i + 1 ][ j + k ], dp[ i ][ j ] + wei2val[ i ][ k ] ); } } } cout << dp[ N ][ M ] << endl; }