https://www.luogu.org/problem/P2473
看数据范围，不是搜索就是状压
于是就开心状压,先不要管他什么期望
DP模型很容易想到，
用f[i,S]表示到了第i轮，宝物是否取过的状态为S的最大期望得分。
但这个模型存在问题：可能在第i轮无法到达状态S****为什么呢？
比如你枚举i的时候是从1开始的,而此时你又要枚举j从0到1<<(n-1),
肯定是不行的啊,那怎么办?
所以，这里把定义换一下
f[i,S]表示在第1轮到第i-1轮内宝物是否取过的状态为S，第i轮到第K轮的最大期望得分，
那么这样就可以通过逆推进行转移了。
转移方程为：
对于任意一个1<=k<=n
1、如果S包含的状态满足取第k种宝物的条件，则可以取或不取。不取则为f[i+1,S]，综合取则为max(f[i+1,S],f[i+1,S|(1<<k-1)]+val[k])。
2、如果S包含的状态不满足取第k种宝物的条件，则不能取，即f[i,S]+=f[i+1,S]。
而这里求的是期望值，上面求的东西覆盖了第i轮取了所有n种宝物的情况，所以在每一个状态计算完之后，把f[i,S]除以n即为期望平均值。
最后答案为f[1,0]。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
int res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
return bo ? ~res + 1 : res;
}
const int M = 105, N = 17;
int K, n, p[N], sta[N];
double f[M][1 << 15];
void chkmax(double &a, double b) {a = max(a, b);}
int main() {
int i, j, k, x; K = read(); n = read();
for (i = 1; i <= n; i++) {
p[i] = read(); while (x = read())
sta[i] = sta[i] | (1 << x - 1);
}
for (i = K; i >= 1; i--) for (j = 0; j < (1 << n); j++) {
for (k = 1; k <= n; k++) if ((j & sta[k]) == sta[k])
f[i][j] += max(f[i + 1][j], f[i + 1][j | (1 << k - 1)] + p[k]);
else f[i][j] += f[i + 1][j];
f[i][j] /= n;
}
printf("%.6lf
", f[1][0]);
return 0;
}