[HNOI2015]亚瑟王(期望+DP）

题解

利用期望的线性性，可以把问题转化为求每一个卡牌造成期望的期望值。

然后我们就需要知道每一个卡牌发动技能的概率。

因为当某一张卡牌发动技能时这一轮会结束，这就很难直接计算了。

我们使用DP

设dp[i][j]为前i张卡牌在r轮中有j张发动技能的概率

i这张牌发动技能的概率就为sigema(j=1,min(r,i-1))f[i-1][j]*(1-(1-p[i])^(m-j))

然后我们考虑如何转移。

当当前卡牌发动技能，dp[i][j]+=dp[i-1][j-1]*(1-(1-p[i])^(m-j+1))

当当前卡牌不发动技能,dp[i][j]+=dp[i-1][j]*(1-p[i])^(m-j)

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int N=;

 int t,n,m;

 double p[N],d[N],pw[N][N],dp[N][N],g[N],ans;

 int main(){

     scanf("%d",&t);

     while(t--){

         memset(dp,,sizeof(dp));

         memset(g,,sizeof(g));

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

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

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

             pw[i][]=;

         }

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

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

                 pw[i][j]=pw[i][j-]*(1.0-p[i]);

             }

         dp[][]=pw[][m];

         dp[][]=g[]=1.0-pw[][m];

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

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

                 if(j!=)dp[i][j]+=(-pw[i][m-j+])*dp[i-][j-];

                 if(i!=j)dp[i][j]+=pw[i][m-j]*dp[i-][j];

             }

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

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

                 g[i]+=dp[i-][j]*(1.0-pw[i][m-j]);

             }

         ans=;

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

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

         }

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

     }

     return ;

 }

巴特西

[HNOI2015]亚瑟王(期望+DP）

题解

最新文章

热门文章