P3239 [HNOI2015]亚瑟王—

题面：亚瑟王

最近考试考期望很自闭啊，没做过这种类型的题，只能现在练一练；

所谓期望，就是状态乘上自己的概率；对于这道题来说，我们要求的是每张牌的伤害乘上打出的概率的和；

当然不是直接乘，因为给的是每轮中这张牌打出的概率，这张牌没打出就要考虑下一张牌，要有一张牌发出技能才能结束一轮；除非一张牌都发不出来；

设每张牌打出的概率是exp[]，答案就是exp[i]*d[i];

exp[i]怎么求？

我们要始终在概率面前一视同仁；

因为牌只有出和不出两种状态，概率和为1；

exp[1]=1-(1-p[1])^r即为1-r轮不出的概率=r轮出的概率；

再考虑第二张：

情况一：如果第1张牌没有发动过技能，那么第22张牌发动技能的概率为1-(1−p[2])r。

情况二：如果第1张牌发动过1次技能，那么在第1张牌发动技能的那一轮，第2张牌绝对不会再发动技能了，因此第2张牌发动技能的概率为1-(1−p[2])r−1。

结合这个例子，可以得到，对于任意的i>1，在第1张牌到第i-1张牌在所有r轮内是否发动技能已经确定的情况下，

第i张牌被发动技能的概率只取决于第1张牌到第i-1张牌中有多少张发动了技能。即如果有j张发动了技能，那么在此情况下第i张牌发动技能的概率为1-(1−p[i])r−j。

（摘自洛古题解https://www.luogu.org/space/show?uid=29936）

设f[i][j]为前i张牌打出j张牌的概率，分别由f[i-1][j-1]和f[i-1][j]转移过来，这张牌打出去和这张牌没打出去；

这张牌打出去了，那么j-1轮中他扔不出去，r-j+1轮中他扔了出去，即为f[i-1][j-1]*(1-(1-p[i])^r-j+1)；

(1-p[i])^r-j+1是剩下的都没打出的概率，用1减去即是j轮打出的概率；

j轮打不出的概率就是f[i-1][j]*(1-(1-p[i])^r-j)

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

typedef double dd;

int T;

int n,r;

dd p[maxn];

int d[maxn];

dd ksm_p[maxn][maxn];

void pre_p()

{

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

    {

        ksm_p[i][]=;

        for(int j=;j<=r;j++)

        {

            ksm_p[i][j]=ksm_p[i][j-]*(-p[i]);

        }

    }

}

dd ans;

dd f[maxn][maxn];//i card j used

dd exp[maxn];

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        ans=;

        memset(f,,sizeof(f));

        memset(exp,,sizeof(exp));

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

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

        {

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

        }

        pre_p();

        f[][]=ksm_p[][r];

        f[][]=exp[]=1.0-ksm_p[][r];

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

        {

            for(int j=;j<=r;j++)

            {

                if(j>i) break;

                if(j!=i) exp[i]+=f[i-][j]*(-ksm_p[i][r-j]);

                if(j) f[i][j]+=f[i-][j-]*(-ksm_p[i][r-j+]);

                if(i!=j) f[i][j]+=f[i-][j]*ksm_p[i][r-j];

            }

        }

        for(int i=;i<=n;i++) ans+=exp[i]*d[i];

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

    }

    return ;

}

巴特西

P3239 [HNOI2015]亚瑟王——概率DP

最新文章

热门文章