WARush

SRMの結果とか、解けた問題のコードを書いていきます

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