yukicoder No.107 モンスター

bitDPの典型問題。bitDPで解く問題は制限がヒントとなるので楽だ。

問題はこちら。

問題

N匹のモンスターがいて、モンスターはいいモンスターと悪いモンスターに分けられる。いいモンスターは1度だけ体力を回復してくれるが、悪いモンスターは体力を削っていく。自分の最大体力は最初100で、悪いモンスターを一匹倒すごとに100ずつ最大体力が増えていく。モンスター全部の相手をしたとき、残すことのできる体力の最大値を答える。なお途中で体力が0となってしまったらそこまでとする。N ≦ 16。

解法

モンスターの相手をする順番を全探索するとO(N!)となってしまう。 どのモンスターを相手したかをBitmaskにより管理して、相手にしたモンスターの数が少ない順にdpで計算していけばいい。dp[どのモンスターを相手にしたか] = （残しうる体力の最大値）とする。D[i]の正負で条件分けしたくなるが、実は下のような書き方をすれば場合分けをする必要もない。体力が0のときにcontinueするのを忘れない。O(2^N NlogN)

N = int(raw_input())
D = map(int,raw_input().split())
bad = sum(1 << i for i in xrange(N) if D[i] < 0)
    
dp = [0]*(1 << N)
dp[0] = 100
for bit in xrange(1 << N):
    for i in xrange(N):
        if dp[bit] == 0 or bit & (1 << i): continue
        beat = bin(bad & bit).count("1")
        dp[bit | 1 << i] = max(dp[bit | 1 << i], min(100*(beat+1), dp[bit]+D[i]))
print dp[(1 << N)-1]

以下同様のことをC++で書いたもの。ビットカウントを自前の関数でやっている。

#include <iostream>
#define rep(i,a) for(int i = 0; i < (a); i++)
using namespace std;

int N, D[17], dp[1 << 17];

int bitcount(int n) {
    int res = 0;
    for(; n; n /= 2) res += n%2;
    return res;
}

int main(void){
    cin >> N;
    rep(i, N) cin >> D[i];
    
    int bad = 0;
    rep(i, N) if (D[i] < 0) bad |= 1 << i;
    
    dp[0] = 100;
    rep(bit, 1 << N) {
        rep(i, N) {
            if (dp[bit] == 0 || bit & 1 << i) continue;
            int beat = bitcount(bit & bad);
            dp[bit | 1 << i] = max(dp[bit | 1 << i], min(100*(beat+1), dp[bit]+D[i]));
        }
    }
    cout << dp[(1 << N)-1] << endl;
    return 0;
}