【BZOJ1076】奖励关（SCOI2008）-状压DP+期望

测试地址：奖励关
做法：本题需要用到状压DP+期望。
首先，在某个时刻掉落了某个宝物，我们是捡还是不捡呢？按照平均情况下最优，也就是期望得分最大，那肯定是按照捡和不捡两种决策做出后，哪个会使期望得分更大而定。具体来说，我们令f(i,j)$f(i,j)$为从第i$i$轮开始，已经获得的宝物集合为j$j$，能得到的最大期望得分，那么我们有以下状态转移方程：
对于每种可能掉落的宝物now$now$，如果当前能取宝物now$now$，对答案有以下贡献：
1nmax(f(i+1,j∪{now})+pnow,f(i+1,j))$\frac{1}{n}max(f(i+1,j\cup \{now\})+p_{now},f(i+1,j))$
而如果不能取，则对答案有1nf(i+1,j)$\frac{1}{n}f(i+1,j)$的贡献。
累加这些贡献，就是我们所求的f(i,j)$f(i,j)$，边界条件为f(n+1,x)=0$f(n+1,x)=0$，答案为f(1,∅)$f(1,\mathrm{\varnothing })$，用状压DP求出即可。
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
int k,n,rq[20]={0};
double p[20],f[110][40010]={0};

int main()
{
    scanf("%d%d",&k,&n);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%lf",&p[i]);
        do
        {
            scanf("%d",&x);
            if (x>0) rq[i]|=(1<<(x-1));
        }while(x);
    }

    for(int i=k;i>=1;i--)
        for(int j=0;j<(1<<n);j++)
            for(int now=1;now<=n;now++)
            {
                if ((j&rq[now])==rq[now])
                    f[i][j]+=max(f[i+1][j|(1<<(now-1))]+p[now],f[i+1][j])/(double)n;
                else f[i][j]+=f[i+1][j]/(double)n;
            }
    printf("%.6lf",f[1][0]);

    return 0;
}