这题有点坑。
很容易看出是状压吧。
但请谨记求概率用正推，期望用逆推。
然而这题为啥我一开始觉得逆推不行呢。
就是因为前置集合。
那么为啥不影响呢。
其实我们逆推的时候也可以判断这个时候可不可以继承，不行就直接不变。
#include<cstdio> #include<iostream> #include<cstring> using namespace std; int Bin[20]; void cs() { Bin[1]=1;for(int i=2;i<=15;i++)Bin[i]=Bin[i-1]*2; } int a[20],qt[20]; double f[110][41000]; int main() { cs(); int n,k,x; scanf("%d%d",&k,&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); while(scanf("%d",&x)!=EOF) { if(x==0)break; qt[i]+=Bin[x]; } } for(int i=k;i>=1;i--) for(int zt=0;zt<=Bin[n]*2-1;zt++) { for(int j=1;j<=n;j++) { if((qt[j]&zt)==qt[j])f[i][zt]+=max(f[i+1][zt],f[i+1][zt|Bin[j]]+a[j]); else f[i][zt]+=f[i+1][zt]; } f[i][zt]/=n; } printf("%.6lf",f[1][0]); return 0; }
原文：http://www.cnblogs.com/AKCqhzdy/p/7857541.html