暴力拍死正解。。

暴力。。
#include<iostream>
#include<cmath>
#include<cstdio>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define INF 1e100
#define inv(x) (1<<((x)-1))
using namespace std;
int cnt,n,val[20],x,S[20];
int treature[110];
double ans;
double temp=1;
int find(int now,int status)
{
	if(now<=cnt)
	{
		int A=0,B=0;
		if ((status&S[treature[now]])==S[treature[now]]) A=val[treature[now]]+find(now+1,status|inv(treature[now]));
		B=find(now+1,status);
		return max(A,B);
	}	
	else
	{
		return 0;
	}
}
int dfs(int now)
{
	if (now<=cnt)
	{
		For(i,1,n)
		{
			treature[now]=i;
			dfs(now+1);
		}
	}
	else
	{
		ans+=find(1,0)*temp;
	}
}
int main()
{
//	freopen("reward.in","r",stdin);
//	freopen("reward.ans","w",stdout);
	scanf("%d%d",&cnt,&n);
	For(i,1,cnt) temp/=n;
	For(i,1,n)
	{
		scanf("%d",&val[i]);
		scanf("%d",&x);
		while (x!=0) 
		{
			S[i]|=1<<(x-1);
			scanf("%d",&x);
		}
	}
	dfs(1);
	printf("%.6lf\n",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}



------------------------

正解？？。。
#include<iostream>
#include<cstring>
#include<cstdio>
#define Ford(i,a,b) for(int i=a;i>=b;i--)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define INF 1e100
#define inv(x) (1<<((x)-1))
using namespace std;
int cnt,n,val[20],x,S[20];
double dp[110][1<<16],res[110][1<<16];
int main()
{
//	freopen("reard.in","r",stdin);
//	freopen("reard.out","w",stdout);
	scanf("%d%d",&cnt,&n);
	For(i,1,n)
	{
		scanf("%d",&val[i]);
		scanf("%d",&x);
		while (x!=0) 
		{
			S[i]|=1<<(x-1);
			scanf("%d",&x);
		}
	}
	Ford(i,cnt,1) 
	{
		For(j,1,n) 
		{
			For(k,0,(1<<n)-1)
			{
				res[i][k]=dp[i+1][k];
				if ((k&S[j])==S[j])
				{
					res[i][k]=max(res[i][k],dp[i+1][k|inv(j)]+val[j]);
				}
			}
			For(k,0,(1<<n)-1) dp[i][k]+=res[i][k]/n;
		}
	}
	printf("%.6lf\n",dp[1][0]);
	fclose(stdin);fclose(stdout);
	return 0;
}