AOJ 2237 The Castle

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2237

解法

bitDP．

dp[i][S][j] := i 番目(0-indexed) の敵と j 番目のねこが戦っていて，生き残っている猫が S であるときの勝てる最大確率

とする．このDPテーブルを最後の敵から最初の敵の順に（つまり後ろから）更新していく．
遷移は dp[i][S][j] = dp[i+1][S][j] * p[j][i] + max(dp[i][S & ~(1 << j)][x]) * (1 - p[j][i]) とかける．第1項は勝った場合，第2項は負けた場合である．
maxを適当に取るとTLEするので，maxを取る位置に注意すること．
また，このままDPテーブルを作るとMLEするので，直前の結果（つまり直後の敵の結果）だけを残してやる．
答えは max(dp[0][(1 << m) - 1][x])．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
double dp[2][1 << 16][16];
double memo[1 << 16];
 
int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<double>> p(m, vector<double>(n));
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n; ++j) {
            cin >> p[i][j];
        }
    }
    for(int S = 1; S < (1 << m); ++S) {
        for(int i = 0; i < m; ++i) {
            dp[n & 1][S][i] = 1;
        }
    }
    for(int i = n - 1; i >= 0; --i) {
        for(int S = 0; S < (1 << m); ++S) {
            for(int j = 0; j < m; ++j) {
                dp[i & 1][S][j] = 0;
            }
            for(int j = 0; j < m; ++j) {
                if(!((S >> j) & 1)) {
                    continue;
                }
                dp[i & 1][S][j] = dp[(i + 1) & 1][S][j] * p[j][i] + memo[S & ~(1 << j)] * (1 - p[j][i]);
            }
            double ma = 0;
            for(int j = 0; j < m; ++j) {
                if((S >> j) & 1) {
                    ma = max(ma, dp[i & 1][S][j]);
                }
            }
            memo[S] = ma;
        }
    }
    double res = *max_element(begin(dp[0][(1 << m) - 1]), end(dp[0][(1 << m) - 1]));
    cout << fixed << setprecision(10) << res << endl;
}