[BZOJ1076][SCOI2008]奖励关

 1 #include<cstdio>
 2 #include<queue>
 3 #include<iostream>
 4 #include<cstring>
 5 using namespace std;
 6 inline int read(){
 7     int ans=0,f=1;char chr=getchar();
 8     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
 9     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
10     return ans*f;
11 }int n,m,a[16],S[16][16],x,MIN;double dp[106][1<<16];
12 double dfs(int x,int s){
13     if(x>m) return 0;
14     if(dp[x][s]>MIN+1) return dp[x][s];
15     dp[x][s]=0;
16     for(int i=(1),ff=1;i<=n;i++,ff=1){
17         for(int j(1);j<=n;j++)if(S[i][j]&&!(s&(1<<j-1))){ff=0;break;}//若不满足选这个物品的条件则退出 
18         if(ff)    dp[x][s]+=max(dfs(x+1,s|(1<<i-1))+a[i],dfs(x+1,s));//当前这个物品满足条件，我们可以选择也可以不选 
19         else dp[x][s]+=dfs(x+1,s);//不满足条件，只能不选 
20     }return dp[x][s]=dp[x][s]/n;//返回,由于求得是期望，要乘上概率，换算一下就是除以n 
21 }int main(){
22     memset(dp,0xcf,sizeof(dp));MIN=dp[0][0];
23     m=read(),n=read();
24     for(int i(1);i<=n;i++){
25         a[i]=read();x=read();
26         while(x) S[i][x]=1,x=read();
27     }printf("%.6lf",dfs(1,0));
28     return 0;
29 }