# CFR 148 E. Porcelain ( DP, Knapsack )

Problem - E - Codeforces

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

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;
}
```