我们设w[i][s]为当前到第i关，手中的物品为s的时候，期望得分为多少，其中s为二进制表示每种物品是否存在。
那么就比较容易转移了w[i][s]=(w[i-1][s']+v[j]) *(1/k)，其中j为枚举当前关可能出现的物品，s‘为s的子集且s’与s只可能相差第j位的物品，且s'包括j物品的所有前提物品，因为每个物品都是随机出现的，所以乘上出现的概率(1/k)，因为我们采取的是最优策略，所以对于每个物品的出现我们还需要和w[i-1][s]取一个max，代表这个物品即使我们能取，也可能不取。
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ //By BLADEVIL
var
n, k :longint;
a :array[..] of longint;
need :array[..] of longint;
w :array[..,..] of extended;
ans :extended; function max(a,b:extended):extended;
begin
if a>b then exit(a) else exit(b);
end; procedure init;
var
i :longint;
y :longint;
begin
readln(n,k);
for i:= to k do
begin
read(a[i]);
y:=;
while y<> do
begin
read(y);
if y<> then need[i]:=need[i] or <<(y-);
end;
end;
end; procedure main;
var
i, j, s :longint;
begin
for i:=n downto do
for s:= to (<<k)- do
for j:= to k do
if need[j] and s=need[j] then
w[i,s]:=w[i,s]+(/k)*max(w[i+,s],w[i+,s or <<(j-)]+a[j]) else
w[i,s]:=w[i,s]+(/k)*w[i+,s]; writeln(w[][]::);
end; begin
init;
main;
end.