#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\n", f[1][0]);
    return 0;
}

从数据范围容易猜到本题应该用状压 dp。

记 $dp_{i,j}$ 表示已经到了第 $i$ 次抛出宝物，已经吃过的宝物的集合为 $j$。易知

$$dp_{i,j}=\frac 1n\cdot\sum_{k=1}^n\begin{cases} \max\{dp[i + 1][j],dp[i + 1][j|1<<(k-1)]+p_k\}, & \text{if can get item }k \\ dp[i + 1][j], & \text{if cannot get item }k \end{cases}. $$

// 2023.05.24

#include<bits/stdc++.h>
using namespace std;

int n,k,p[16],r[16];
double dp[102][1<<15];

int main(){
    scanf("%d%d",&k,&n);
    for(int i=1;i<=n;i++){
        scanf("%d",p+i);
        int x; scanf("%d",&x);
        while(x)
            r[i]|=1<<x-1,
            scanf("%d",&x);
    }
    for(int i=k;i>=1;i--)
        for(int j=0;j<(1<<n);j++){
            for(int t=1;t<=n;t++)
                if((j|r[t])==j)
                    dp[i][j]+=max(dp[i+1][j|(1<<(t-1))]+p[t],dp[i+1][j]);
                else dp[i][j]+=dp[i+1][j];
            dp[i][j]/=n;
        }
    printf("%.6lf\n",dp[1][0]);
    return 0;
}