BZOJ1076 [SCOI2008]奖励关 概率 状态压缩动态规划

时间：2023-05-09 14:53:56

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

题目传送门 - BZOJ1076

题意概括

　　有n个东西，k次扔出来。每次等概率扔出其中一个。

　　你可以拿这个东西，但是有条件，得在拿到指定东西之后再拿，否则白拿。

　　拿到一个东西，会获得其权值。可以是负数。

题解

　　状压dp跑一发。

　　一开始想写正着dp的，因为我觉得这样听挺容易想的。

　　然而网上的大牛都说是倒着的。于是我倒着了。

　　方程是这样的：

　　dp[i][j]表示扔出来i次之后，状态为j，在这之后可以得到的最大收益。

　　dp[i][j]=(∑F[k])/n

　　F[k]分两种情况。如果在状态j的情况下可以取k，那么F[k] = max(dp[i+1][j],dp[i+1][j | (1<<k)] + v[k])

　　　　否则F[k] = dp[i+1][j]

　　根据意义，最后输出dp[0][0]即可。

代码

#include <cstring>

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <cmath>

using namespace std;

const int N=+,M=+,S=(<<)+;

int n,m,v[N],pre[N];

double dp[M][S];

int main(){

    scanf("%d%d",&m,&n);

    memset(pre,,sizeof pre);

    for (int i=,p;i<n;i++){

        scanf("%d",&v[i]);

        while (scanf("%d",&p)&&p!=)

            pre[i]|=<<(p-);

    }

    for (int i=m-;i>=;i--)

        for (int j=;j<(<<n);j++){

            dp[i][j]=;

            for (int k=;k<n;k++)

                if ((pre[k]&j)==pre[k])

                    dp[i][j]+=max(dp[i+][j],dp[i+][j|(<<k)]+v[k]);

                else

                    dp[i][j]+=dp[i+][j];

            dp[i][j]/=n;

        }

    printf("%.6lf",dp[][]);

    return ;

}

相关文章