奖励关

题目链接：https://www.luogu.com.cn/problem/P2473

思路：设f[i,j]表示当前吃的状态为i,当前是第j次抛的按最优决策的期望得分。然后先找到已知条件进行逆推。对于所有的k。

当k可要可不要或必须吃时：f[i,j]+=max(f[i+1,j],f[i+1,j|(1<<k)])

当k不可以吃时：f[i,j]+=f[i+1,j]

#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[16],b[16];
double dp[110][1<<16];
int main()
{
    int n,m;
    cin>>m>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        int x;
        while(1)
        {
            cin>>x;
            if(!x)
                break;
            b[i]|=(1<<(x-1));
        }
    }
    for(int i=m; i>=1; i--)
    {
        for(int j=0; j<(1<<n); j++)
        {
            for(int k=0; k<n; k++)
            {
                if((j&b[k])==b[k])
                    dp[i][j]+=max(dp[i+1][j],dp[i+1][j|(1<<k)]+a[k]);
                else
                    dp[i][j]+=dp[i+1][j];
            }
            dp[i][j]/= n;
        }
    }
    printf("%.6lf",dp[1][0]);
}