首页 > 代码库 > BZOJ 1076 奖励关

BZOJ 1076 奖励关

注意几点:

1.为什么要逆推?由此状态可以轻易算出彼状态是否可行,而彼状态却无法轻易还原为此状态。

2.为什么可以逆推?假设时光倒流了。。。。23333

3.注意位运算的准确,大胆写方程。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int k,n,p[150],x,limit[150];double dp[150][(1<<16)-1];int main(){    scanf("%d%d",&k,&n);    for (int i=1;i<=n;i++)    {        scanf("%d",&p[i]);        for (;;)        {            scanf("%d",&x);            if (!x) break;            limit[i]|=(1<<(x-1));        }    }    for (int i=k;i>=1;i--)    {        for (int s=0;s<=(1<<n)-1;s++)        {            dp[i][s]=0;            for (int k=1;k<=n;k++)            {                if ((s&limit[k])==limit[k])                    dp[i][s]+=max(dp[i+1][s],dp[i+1][s|(1<<(k-1))]+p[k]);                else dp[i][s]+=dp[i+1][s];            }            dp[i][s]/=n;        }    }    printf("%.6lf\n",dp[1][0]);    return 0;}

 

BZOJ 1076 奖励关