题意：$n$种宝物，出现$k$次每次一种，每种宝物有价值和吃掉它之前必须要吃掉的宝物的集合，求采取最优策略的期望最大价值

1<=k<=100,1<=n<=15，分值为[-10^6,10^6]内的整数。

---

 

看到$n$应该想到状压....

$f[i][s]$表示前$i$次已经吃掉的集合为$s$的期望最大值

然而正推的话，答案是谁呢？

所以倒推，表示这个状态到结束得到的期望最大值

转移枚举出现的宝物，最后乘上概率$\frac{1}{n}$

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll;const int N=105,S=1<<15;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int m,n,val[N],need[N];double f[N][S];int main(){    freopen("in","r",stdin);    m=read();n=read();    for(int i=0;i
          
           =1;i--) for(int s=0;s