[洛谷 3239,loj 2112][HNOI2015]亚瑟王

题目链接

https://www.luogu.com.cn/problem/P3239

https://loj.ac/problem/2112

题解

根据期望的线性性,我们可以把每张牌使用的概率算出来,再把每张牌的期望伤害值相加即可得到答案。

现在问题变成了这个概率怎么求。

设第 \(i\) 张牌使用的概率为 \(g_i\)。

对于第一张牌,容易得知:

$$g_1=1-(1-p_1)^r$$

对于第二张牌,我们发现这个概率和第一张牌是否被取有关:

  • 如果第一张牌被取了:由于第一张牌被取后当前轮立刻结束,因此我们只有 \(r-1\) 轮来决定是否取第二张牌。
  • 如果第一张牌没被取:我们有 \(r\) 轮来决定是否取第二张牌。

设 \(f_{i,j}\) 表示 \(r\) 轮中考虑前 \(i\) 张牌,取 \(j\) 张的概率。边界显然是 \(f_{0,0}=1\)。

现在我们考虑第 \(i\) 张牌:

  • 如果不取第 \(i\) 张牌:\(f_{i,j}=f_{i-1,j} \times (1-p_i)^{r-j}\)(取了 \(j\) 张意味着有 \(j\) 轮都没有考虑第 \(i\) 张牌);
  • 如果取第 \(i\) 张牌:\(f_{i,j}=f_{i-1,j-1} \times (1-(1-p_i)^{r-j+1})\)。

有了这些信息,结合前面的推导,\(g_i\) 就很好推了:

$$g_i=\sum_{j=0}^r f_{i-1,j} \times (1-(1-p_i)^{r-j})$$

#include <cstdio>
#include <cstring>
#include <cmath>
double f[255][255],g[255],p[255];
int d[255];
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  memset(f,0,sizeof(f));
  memset(g,0,sizeof(g));
  int n,r;
  scanf("%d%d",&n,&r);
  f[0][0]=1;
  for(int i=1;i<=n;i++)
   scanf("%lf%d",&p[i],&d[i]);
  for(int i=1;i<=n;i++)
   for(int j=0;j<=r;j++)
   {
    double tmp=pow(1-p[i],r-j);
    f[i][j]=f[i-1][j]*tmp+(j>0)*f[i-1][j-1]*(1-tmp*(1-p[i]));
   }
  g[1]=(1-pow(1-p[1],r));
  for(int i=2;i<=n;i++)
   for(int j=0;j<=r;j++)
    g[i]+=f[i-1][j]*(1-pow(1-p[i],r-j));
  double ans=0;
  for(int i=1;i<=n;i++)
   ans+=g[i]*d[i];
  printf("%.10lf\n",ans);
 }
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据