P2473 [SCOI2008] 奖励关
题解：
很容易想到 \(f_{i,S}\) 为第 \(i\) 轮，每个物品选取情况为 \(S\) 的最大期望。
但这样子转移时选择宝物的概率并不是平均的，很难处理。
那么考虑逆推，改状态为前 \(i-1\) 轮的选取状态为 \(S\)，\(i\) 到 \(k\) 轮的最大期望。
转移方程即为：
\[f_{i,S} \leftarrow \max(f_{i+1,S|(1<<(j-1))}+w_j (p_j \in S),f_{i+1,S})
\]
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 15, K = 100;
int k, n;
ll w[N + 7];
int p[N + 7];
double f[K + 7][(1 << N) + 7];
int main(){ios::sync_with_stdio(0);cin.tie(0);cin >> k >> n;for(int i = 1; i <= n; i++){cin >> w[i];int x = -1;while(1){cin >> x;if(!x) break;p[i] |= (1 << (x - 1));}}for(int i = k; i; i--){for(int S = 0; S < (1 << n); S++){for(int j = 1; j <= n; j++){if((S & p[j]) == p[j]){f[i][S] += max(f[i + 1][S], f[i + 1][S | (1 << (j - 1))] + w[j]);}else f[i][S] += f[i + 1][S];}f[i][S] /= n;}}printf("%.6lf\n", f[1][0]);return 0;
}