「Bzoj 1076」「SCOI2008」奖励关 (状压概率期望DP)

Bzoj 1076
采取最优策略很关键，这会使每一步都要取$max$或者$min$然后再相加
设$dp(i,S)$为前$i$次投掷，当前吃的种类集合状态为$S$时到游戏结束的得分期望。
那么如果一个$S$不符合某个物品$j$的前提集合，那么$dp(i, S) = \frac{1}{n}dp(i +1, S)$
否则$dp(i, S) = \sum \frac{1}{n}max(dp(i+1, s), dp(i+1, S \cup j)+p_j)$
然后注意方向。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXK = 100 + 5, MAXN = 15 + 2; 
int K, n, p[MAXN], s[MAXN];
db dp[MAXK][1 << MAXN];
void clean() {
    ms(s, 0);
}
void solve() {
    clean();
    for (int i=1;i<=n;i++) {
        scanf("%d", &p[i]);
        int x; scanf("%d", &x);
        while (x != 0) s[i] += (1 << (x - 1)), scanf("%d", &x);
    }
    for (int i=K;i>0;i--) {
        for (int S=0;S<(1<<n);S++) {
            for (int j=1;j<=n;j++) {
                if ((S & s[j]) == s[j]) {
                    dp[i][S] += max(dp[i + 1][S], dp[i + 1][S | (1 << (j - 1))] + p[j]);
                } else dp[i][S] += dp[i + 1][S];
            }
            dp[i][S] /= (db)n;
        }
    }
    printf("%.6f\n", dp[1][0]);
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    scanf("%d%d", &K, &n), solve();
    return 0;
}