0w1

CFR 148 E. Porcelain ( DP, Knapsack )

Problem - E - Codeforces

題意:
有 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;
}