Description：

游戏有 $k$ 轮，每轮会随机产生一个物品，可以选择是否收下，每个宝物有价值，且每个宝物只有在获得了一些前提物品才能获得，问最优决策下期望能获得多少价值。

$1\le n \le 15$

Solution：

这数据范围应该就是状压了，设 $f[k][S]$ 表示第 $k$ 轮时状态为 $S$ 时一直到最后能获得多少收益，转移要倒推，之所以是倒推是因为先后手决策不同，可能会为了后面的而选择现在的，如果正推的话决策可能会分散，即分开成多种情况最后无法统计相同操作的价值，所以倒推，如果这个可以选的话就从选和不选中选一个最大的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int k,n;

#define MAXN 16

#define MAXK 101

int val[MAXN];

int pre[MAXN];

double f[MAXK][1 << MAXN];

int main()

{

	scanf("%d%d",&k,&n);

	int p;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&val[i]);

		while(scanf("%d",&p) && p != 0)pre[i] |= (1 << (p - 1));

	}

	int tot = (1 << n) - 1;

	for(int w = k;w >= 1;--w)

	{

		for(int b = 0;b <= tot;++b)

		{

			for(int i = 1;i <= n;++i)

			{

				if((pre[i] & b) == pre[i])

				{

					f[w][b] += max(f[w + 1][b],f[w + 1][b | (1 << (i - 1))] + val[i]);

				}

				else f[w][b] += f[w + 1][b];

			}

			f[w][b] /= n;

		}

	} 

	printf("%.6lf\n",f[1][0]);

	return 0;

}