发现自己已经把期望dp忘光了...
其实本质上非常简单，就是利用状压的思想跑期望
首先很容易设计出状态：记状态f[s][i]表示到了第i个点，之前已选过的点的状态为s时所能获得的最大期望得分
但是会发现这样做没法转移（你可以试一下，我做了半个点做得原地爆炸）
但是我们知道，期望dp常见的策略是从后向前，逆向转移
所以我们修改一下状态：记状态f[s][i]表示到了第i个点选的点集为s时，i-k所能获得的最大期望
这样有转移方程：
（x的前提在s中）
（x的前提不在s中）
最后将f[s][i]除以n，得到的即为答案
最后输出f[0][1]即可
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
double dp[105][(1<<15)+5];
double f[(1<<15)+5];
int k,n;
int sit[20];
double v[20];
int main()
{
scanf("%d%d",&k,&n);
for(int i=1;i<=n;i++)
{
scanf("%lf",&v[i]);
while(1)
{
int x;
scanf("%d",&x);
if(!x)
{
break;
}
sit[i]|=(1<<(x-1));
}
}
for(int i=k;i>=1;i--)
{
for(int j=0;j<(1<<n);j++)
{
for(int o=1;o<=n;o++)
{
if((sit[o]&j)==sit[o])
{
dp[i][j]+=max(dp[i+1][j|(1<<(o-1))]+v[o],dp[i+1][j]);
}else
{
dp[i][j]+=dp[i+1][j];
}
}
dp[i][j]*=1.0/(double)n;
}
}
printf("%.6lf
",dp[1][0]);
return 0;
}