题解
一道经典的期望DP题。
看到数据范围就很自然会想到进行状态压缩。因此，设$f(i, S)$为完成第$i$轮及以后，已经完成的情况为$S$的期望收益的最大值。因此有：
如果第$j$个抛出的宝物能吃，那么就有$f(i, S) = \max \lbrace f(i + 1, S \bigcup {j}) + P[j], f(i+1, S) \rbrace$，代表选择吃或者不吃。
如果第$j$个抛出的宝物不能吃，那么就有$f(i, S) = f(i+1, S)$，代表只能不吃。
完成这$n$个选项后，$f(i, S)$要除以$n$。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
41
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int k, n, a[105], restraint[105] = {0};
double f[105][70005] = {0};
void init(){
k = read(), n = read();
for(int i = 0; i < n; ++i){
a[i] = read();
int t;
while(t = read()) restraint[i] |= (1 << (t - 1));
}
}
void solve(){
int bin = (1 << n);
for(int i = k; i >= 1; --i){
for(int j = 0; j < bin; ++j){
for(int t = 0; t < n; ++t){
if((restraint[t] & j) == restraint[t])
f[i][j] += max(f[i + 1][j], f[i + 1][j | (1 << t)] + a[t]);
else
f[i][j] += f[i + 1][j];
}
f[i][j] *= 1.0 / n; //n个来源
}
}
printf("%.6lf\n", f[1][0]);
}
int main(){
init();
solve();
return 0;
}