Bzoj 1076(状压概率期望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)$
然后注意方向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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;
}

------ 本文结束 ------