CodeDevil

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1076

【题意】

见题面。。。orz

【题解】

状压DP，从后往前推就行了

【代码】

#include <cstdio>

#include <iostream>

using namespace std;

double dp[110][100000];

int n,m,t;

int v[50],cnt[50];

int main()

{

    int i,j,k;

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

    for (i=1;i<=m;i++)

    {

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

        while (t)

        {

            cnt[i]+=(1<<(t-1));

            scanf("%d",&t);

        }

    }

     

    for (i=n;i>=0;i--)

        for (j=0;j<=(1<<m)-1;j++)

        {

            for (k=1;k<=m;k++)

                if ((cnt[k]&j)==cnt[k])

                   dp[i][j]+=max(dp[i+1][j],dp[i+1][j|(1<<(k-1))]+v[k]);

                else

                    dp[i][j]+=dp[i+1][j];

            dp[i][j]=dp[i][j]*1.0/m;

        }

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

    return 0;

}