原题链接：https://www.luogu.com.cn/problem/P2473
题意解读：有n中宝物，每个宝物有得分，有能不能吃的条件（之前吃过哪几种宝物才能吃当前宝物），抛k次，求最高得分的期望。
解题思路：
如果做过https://www.cnblogs.com/hackerchef/p/18944242这道题，那么不难想到，这样的题用记忆化搜索来思考更顺畅。
设从初始节点开始：状态为0，二进制位1表示已经吃过的宝物
对于每一个节点，设dp(cnt, status)表示从抛出第cnt次宝物开始，已吃宝物状态为status时，最终能得到的最高得分期望
答案必须是dp(1, 0)
接下来看如何转移？
对于某一次抛出的宝物，一共有n种可能，通过枚举n个宝物，判断当前状态status是否满足吃该宝物，
如果不能吃，则有dp(cnt, status) = dp(cnt + 1, status)
如果能吃，则可以吃也可以不吃，两种情况取max，则有dp(cnt, status) = max(dp(cnt + 1, status), dp(cnt + 1, status |= (1 << i - 1)))
由于求期望，每一次宝物都有n中可能，因此求出的dp(cnt, status) /= n
状态的表示以及判断当前状态能否吃某个物品，就借助了状态压缩
最后，为了进一步提升递归效率，加上记忆化搜索即可。
100分代码：
#include <bits/stdc++.h>
using namespace std;const int N = 16, K = 105, INF = 1e9;int k, n;
int p[N], s[N];
double f[K][1 << N];//从抛第cnt个宝物开始，已获得宝物状态为status，能得到的最多分数的期望
double dp(int cnt, int status)
{double res = 0;if(cnt > k) return res;if(f[cnt][status] > -INF) return f[cnt][status]; //记忆化剪枝for(int i = 1; i <= n; i++) //第cnt个宝物有n中可能{if((status & s[i]) == s[i]) //对应的宝物是否能满足能吃的条件{res += max(dp(cnt + 1, status), dp(cnt + 1, status | (1 << i - 1)) + p[i]); //满足条件，可以选择吃或不吃，取max}else res += dp(cnt + 1, status); //不满足能吃的条件}return f[cnt][status] = res / n; //除以n即计算期望，同时记忆化
}int main()
{cin >> k >> n;for(int i = 1; i <= n; i++){int x;cin >> p[i];while(cin >> x && x != 0){s[i] |= (1 << x - 1);}}for(int i = 1; i <= k; i++)for(int j = 0; j < 1 << n; j++)f[i][j] = -INF;cout << fixed << setprecision(6) << dp(1, 0);return 0;
}