我就是一个成功的反例…
直接正着推，直接推成了憨憨
思路
首先我们看题：
n < = 15 n<=15 n<=15，灵光一闪。
淦哪！我们可以很肯定这是一个状压 D P + DP+ DP+期望 D P DP DP。
状态也十分清楚：
f
[
i
]
[
j
]
f[i][j]
f[i][j]为从到第
i
i
i轮，状态为
j
j
j的最大期望值。然后再推到最后…
如果你到了这个地步，那你就成功地和我一样成为铁憨憨了。
因为 f [ i ] [ j ] f[i][j] f[i][j]这个状态可能在之前的 i i i轮中达不到 j j j这个状态…
那怎么办？怎么办！凉拌抄鸡蛋 逆着推，就可以避免这种错误了一把辛酸泪。
我们定义 f [ i ] [ j ] f[i][j] f[i][j]为从第 k k k轮到第 i i i轮，状态为 j j j的最大期望值。
如果我们 j j j包含的状态满足取第 k k k宝物的条件，我们就可以取这个宝物。当然也可以不取。
if((j & sta[k])==sta[k]) //可以取
f[i][j]+=max(f[i+1][j],f[i+1][j|(1<<(k-1))]+a[k]);
否则，我们就不取这个宝物，我们取不到！
f[i][j]+=f[i+1][j];
我们把每个宝物都考虑后，直接把 f [ i ] [ j ] f[i][j] f[i][j]除以 n n n。因为我们的各个宝物的概率依然均为 1 n \frac{1}{n} n1。
f[i][j]/=n;
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=20,maxk=105;
int n,k,a[maxn],sta[maxn];
double f[maxk][1<<maxn];
//f[i][k]为第i~k轮，状态为k
int read(int &x) {
int f=1; x=0; char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0' && ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
x*=f;
return 1;
}
int main() {
read(k),read(n);
for(int i=1,x;i<=n;i++) {
read(a[i]);
while(read(x) && x) sta[i]|=(1<<(x-1)); //前提宝物集合
}
for(int i=k;i;i--) { //逆推
for(int j=0;j<(1<<n);j++) { //枚举状态
for(int k=1;k<=n;k++) { //枚举宝物
if((j & sta[k])==sta[k]) //可以选这个宝物
f[i][j]+=max(f[i+1][j],f[i+1][j|(1<<(k-1))]+a[k]);
else f[i][j]+=f[i+1][j]; //不可以选这个宝物
}
f[i][j]/=n; //概率
}
}
printf("%.6lf",f[1][0]);
return 0;
}