BZOJ 1076 奖励关

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int k,n,p[150],x,limit[150];
double dp[150][(1<<16)-1];
int main()
{
    scanf("%d%d",&k,&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&p[i]);
        for (;;)
        {
            scanf("%d",&x);
            if (!x) break;
            limit[i]|=(1<<(x-1));
        }
    }
    for (int i=k;i>=1;i--)
    {
        for (int s=0;s<=(1<<n)-1;s++)
        {
            dp[i][s]=0;
            for (int k=1;k<=n;k++)
            {
                if ((s&limit[k])==limit[k])
                    dp[i][s]+=max(dp[i+1][s],dp[i+1][s|(1<<(k-1))]+p[k]);
                else dp[i][s]+=dp[i+1][s];
            }
            dp[i][s]/=n;
        }
    }
    printf("%.6lf\n",dp[1][0]);
    return 0;
}