EmptyTheBox [SRM 782 Div1 Easy]

前提知識

• O(3^N)のbitDP

解説

簡単にまとめておく。

サイコロで出せる合計の目の上限は2Dなので、Tが2Dを超えていたら、その部分は絶対余る。
なので、Tは2Dまでを考えればいい。
すると、bitDPができることに気が付く。
dp[msk] := 残っているペナルティトークンの集合がmskであるときの、ペナルティの最小期待値
遷移はO(3^N)のbitDPで頑張る。
サイコロである目が出たときに消す操作が複数パターンあったら、DPを見て最小期待値のものを選んでいけばいい。

double dp[1 << 12];
double opt[1010];
bool changed[1010];
double p[13];
struct EmptyTheBox {
    double minExpectedPenalty(int D, int T) {
        double ng = 0;
        while (D * 2 < T) ng += T, T--;
        rep(d1, 1, D + 1) rep(d2, 1, D + 1) p[d1 + d2] += 1.0 / D / D;

        rep(msk, 0, 1 << T) {
            rep(i, 1, D * 2 + 1) opt[i] = inf, changed[i] = false;
            for (int msk2 = msk; msk2 > 0; msk2 = (msk2 - 1) & msk) {
                int cn = 0;
                rep(i, 0, T) if ((msk2 & (1 << i))) cn += i + 1;
                changed[cn] |= chmin(opt[cn], dp[msk - msk2]);
            }

            int tot = ng;
            rep(i, 0, T) if (msk & (1 << i)) tot += i + 1;

            rep(i, 2, D * 2 + 1) {
                if (changed[i]) dp[msk] += opt[i] * p[i];
                else dp[msk] += 1.0 * tot * p[i];
            }
        }
        return dp[(1 << T) - 1];
    }
};