P3239 [HNOI2015]亚瑟王

思路

神仙概率dp

由于期望的线性性质，能够想到最后要求的期望价值就是把每个卡牌发动的概率\(g_i\)乘上伤害\(val_i\)之后加到一起

然后怎么求\(g_i\)呢，肯定是要dp的

我想了例如dp[i][j]表示第i张纸牌还有j次的考虑机会，dp[i][j]表示第i轮牌j发动的概率，但是都没有想出转移

发现每个牌一局游戏只能够发动一次，而且前面发动一次之后后面的纸牌不能再发动

然后发现第0张纸牌发动的概率是\(p[0]=(1-(1-k[0])^r)\)（总概率-每一回合都不放的概率为有1回合放的概率）

第一张纸牌发动会受到第0张纸牌的影响，如果第0张纸牌不发动，第一张发动的概率就是\(p[1]=(1-(1-k[1])^r)\)，如果第0张发动，则概率为\(p[1]=(1-(1-k[1])^{r-1})\)，每一张牌发动的概率只依赖于前面，且只依赖于有几张纸牌发动，所以可以把有几张纸牌发动压进状态里，然后就可以dp了

设dp[i][j]表示前i张纸牌，有j张发动的概率

决策自然是有两种：第i张发动/第i张不发动

如果第i张发动，则前面i-1张中有j-1张发动，第i张发动的概率为\(p[i]=(1-(1-k[i])^{r-j+1})\)

如果第i张不发动，则前面i-1张中有j张发动，第i张不发动的概率为\(p[i]=(1-k[i])^{r-j}\)

然后就得出状态转移方程为\(dp[i][j]=dp[i-1][j-1]*(1-(1-k[i])^{r-j+1})+dp[i-1][j]*(1-k[i])^{r-j}\)

所以\(g_i=\sum_{j=0}^{min(i-1,r)}dp[i-1][j]*(1-(1-k[i])^{r-j})\)

然后没了

注意多组数据，数组要清空

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

int T,n,m,val[230];

double k[230],dp[230][140],g[230];

double pow(double a,int b){

    double ans=1;

    while(b){

        if(b&1)

            ans=(ans*a);

        a=(a*a);

        b>>=1;

    }

    return ans;

}

int main(){

    // freopen("2.in","r",stdin);

    // freopen("test.out","w",stdout);

    scanf("%d",&T);

    while(T--){

        double ans=0;

        memset(val,0,sizeof(val));

        memset(k,0,sizeof(k));

        memset(dp,0,sizeof(dp));

        memset(g,0,sizeof(g));

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

        for(int i=1;i<=n;i++){

            scanf("%lf %d",&k[i],&val[i]);

        }

        // printf("ok\n");

        dp[0][0]=1;

        for(int i=1;i<=n;i++)

            for(int j=0;j<=min(i,m);j++){

                if(j>0){

                    dp[i][j]+=dp[i-1][j-1]*(1-pow((1-k[i]),m-j+1));

                }

                dp[i][j]+=dp[i-1][j]*(pow(1-k[i],m-j));

            }

        // printf("ok\n");

        for(int i=1;i<=n;i++)

            for(int j=0;j<=min(i-1,m);j++)

                g[i]+=dp[i-1][j]*(1-pow(1-k[i],m-j));

        for(int i=1;i<=n;i++)

            ans=ans+g[i]*val[i];

        printf("%.10lf\n",ans);

    }

    return 0;

}

巴特西

P3239 [HNOI2015]亚瑟王

思路

代码

最新文章

热门文章