题意：$n$种宝物，出现$k$次每次一种，每种宝物有价值和吃掉它之前必须要吃掉的宝物的集合，求采取最优策略的期望最大价值
1<=k<=100,1<=n<=15，分值为[-10^6,10^6]内的整数。
看到$n$应该想到状压....
$f[i][s]$表示前$i$次已经吃掉的集合为$s$的期望最大值
然而正推的话，答案是谁呢？
所以倒推，表示这个状态到结束得到的期望最大值
转移枚举出现的宝物，最后乘上概率$\frac{1}{n}$
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=,S=<<;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int m,n,val[N],need[N];
double f[N][S];
int main(){
freopen("in","r",stdin);
m=read();n=read();
for(int i=;i<n;i++){
val[i]=read();int x=read();
while(x) need[i]|=(<<(x-)),x=read();
}
int All=<<n;
for(int i=m;i>=;i--)
for(int s=;s<All;s++){
for(int j=;j<n;j++){
if((s&need[j])==need[j]) f[i][s]+=max(f[i+][s],f[i+][s|(<<j)]+val[j]);
else f[i][s]+=f[i+][s];
}
f[i][s]/=n;
}
printf("%.6lf",f[][]);
}