离散型概率
状压DP
#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <sstream> #include <iostream> #include <cstdlib> #include <set> #include <map> #include <stack> #include <queue> #include <vector> #include <algorithm> #include <functional> using namespace std; #define ll long long #define re register #define pb push_back #define mp make_pair #define fi first #define se second #define P pair<int,int> void read(int &a) { a=0; int d=1; char ch; while(ch=getchar(),!isdigit(ch)) if(ch=='-') d=-1; a=ch^48; while(ch=getchar(),isdigit(ch)) a=(a<<3)+(a<<1)+(ch^48); a*=d; } void write(int x) { if(x<0) putchar(45),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } double f[105][1<<15]; int sta[20],a[20]; int main() { int k,n; read(k); read(n); for(re int i=1;i<=n;i++) { read(a[i]); int x; read(x); if(!x) continue; sta[i]|=(1<<x-1); while(x) { read(x); if(!x) break; sta[i]|=(1<<x-1); } } for(re int i=1;i<=k;i++) { for(re int j=0;j<(1<<n);j++)///枚举状态 { for(re int l=1;l<=n;l++)///枚举物品 if((j&sta[l])==sta[l])///判断该状态能否转移 f[i][j]+=max(f[i-1][j],f[i-1][j|(1<<l-1)]+a[l]); else f[i][j]+=f[i-1][j]; f[i][j]/=n;///乘上该事件发生的概率 } } printf("%.6lf",f[k][0]); return 0; }