https://blog.csdn.net/tenkuo/article/details/154778293

根据题面，可以发现比较关键的字眼：集合，期望。可以判断，本题是期望DP加状态压缩 对于状态压缩的题，就是把选或不选状态用一个数的二进制表示。 即可以设计状态dp[i][K]为第i次掉落物时已选的掉落物的集合为K，j为当前取第几个物品 /*所以可以写出方程式： 如果满足当前所取物品的需求集合 dp[i][K]+=max(dp[i+1][K],dp[i+1][K|(1<<(j-1))])+p[j]); 若不满足 dp[i][K]+=dp[i+1][K] */ 至于为什么是i+1转移，是因为期望DP一般是从结束状态倒推起始状态，在过程中计算答案 而且因为正推的话有些情况在转移时选择宝物的概率并不是平均的（有宝物合集的限制）。 这样就会导致结果出现问题，且最终答案的状态表示十分麻烦，因此选择倒推。

#include<bits/stdc++.h>
using namespace std;
const int N=210;
double dp[110][1<<16];
int need[N];
int p[N];
int main(){
    int m,n;scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&p[i]);
        int x;
        while(scanf("%d",&x)&&x){
            need[i]|=(1<<(x-1));//表示需求集合 
        }
    }
    for(int i=m;i>=1;i--){//第几轮 
        for(int k=(1<<n)-1;k>=0;k--){//当前集合 
            for(int j=1;j<=n;j++){//当前为第几个物品 
                if((need[j]&k)==need[j]){//满足需求集合 
                    dp[i][k]+=max(dp[i+1][k], dp[i+1][k|(1<<(j-1))]+double(p[j]));
                }
                else dp[i][k]+=dp[i+1][k];
            }
            dp[i][k]/=n;//每个物品为1/n，记得乘上1/n 
        }
    }
    printf("%.6lf",dp[1][0]);
}