题解 P2473 【[SCOI2008]奖励关】

寒冰大大 · 2020-03-31 16:57:27 · 题解

P2473 SCOI2008奖励关

题面懒得描述。

根据题意列出dp方程f[i][S],即第i轮情况为s的平均分。

考虑顺序枚举，最后得到的答案有15^{100}种可能性，显然你需要手写高精，并且不可能刚开始就吃掉所有的点，顺序还需要加几个数组来标记一下当前可能到的情况，所以考虑倒序枚举。

然后写代码，发现如果先枚举i,j,在枚举本轮情况，最后并不好处理平均数（其实就多了个循环）,于是为了偷懒先枚举i再枚举k然后再j.

考虑转移，显然转移要考虑这一层能否对下一层产生影响，那就要考虑能不能包含j这个点所需的前提宝物，如果可以的话，就能获得价值为a[j]的分数，由于是倒序枚举，所以我们转移回来f[i][k]（原先是转移到f[i][k']，k'包含j）

最后f[1][0]就是我们要的答案了

最后代码奉上

#include<touwenjian.h>

using namespace std;

double f[110][75536];
int s[20],a[20];
int n,m;

int main()
{
    scanf("%d %d",&m,&n);
    int i,j,t;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        while(1)
        {
            scanf("%d",&t);
            if(t==0) break;
            s[i]|=1<<(t-1);
        }
    }
    int k;
    for(i=m;i;i--)
    for(k=0;k<=(1<<n)-1;k++)
    {
        for(j=1;j<=n;j++) if((s[j]&k)==s[j]) f[i][k]+=max(f[i+1][k],f[i+1][k|(1<<(j-1))]+a[j]);
        else f[i][k]+=f[i+1][k];
        f[i][k]=f[i][k]*1.0/n;
    }
    printf("%.6lf",f[1][0]);
}