Codeforces #178 Div2 B "Shaass and Bookshelf"
問題
http://codeforces.com/contest/294/problem/B
訳
n冊の本がある。全ての本が入りきるだけの本棚を作りたいのだが、
なるべく小さく作りたい。
各本の幅と、奥行きの長さが与えられる。幅は1か2のどちらかである。
また、本の高さは全て一緒である。
本を収納するときは、まず始めにいくつかの本を選び、
それらを立てて(普通に)入れていく。
それから、残った本を横にして、入れてある本の上に乗せていく。
上に乗せる本は、その長さ(奥行き)の合計が
下にある本の長さ(幅)の合計を超えてはならない。
イメージ図
下に入れる本の幅の最小値を出力せよ。
制約
1 <= n <= 100
1 <= 本の奥行き <= 100
本の幅 = 1か2
考えた事
貪欲かな・・奥行きが短い本を貪欲に上に乗せてみよう。
手元のサンプルだと正しいな。ポチっとな(Submit)
WA
ま・・ま~ねま~ね。
そ、そうだと思ったようん。
各本を上に乗せるか下に入れるかをメモ再帰でやろう。
え~と、状態数はいくつだ?
本の数 * 下の幅 * 上の幅だから
100 * (100*2) * (100*100)で・・・
2億・・か・・。
まあ、メモを取るべきものは限られてるから大丈夫だろう。
ポチっとな。
MLE
2億 * 4byteで800Mbyteだったやべぇ・・・
まてよ・・上の幅を10000も持たせる必要ないよな。
だって200超えたら絶対無理だもんね。
メモを100 * (100*2) * 200にして・・ポチっとな
AC
ふぅ・・・
ソースコード
const int INF = 1000000; int N, t[110], w[110]; int memo[110][210][210]; int dfs( int i, int down, int up ){ if( i == N ){ if( down >= up ){ return down; }else{ return INF; } } int& m = memo[i][down][up]; if( m != -1 ) return m; // 下に置く int res = dfs( i+1, down + t[i], up ); // 上に乗せる if( up + w[i] <= 200 ){ res = min( res , dfs( i+1, down, up + w[i] )); } return m = res; } int main() { cin >> N; for( int i = 0; i < N; i++ ){ cin >> t[i] >> w[i]; } memset( memo, -1, sizeof(memo) ); printf( "%d\n", dfs(0, 0, 0) ); }