目录
显示
题目链接
https://www.luogu.com.cn/problem/P3239
题解
根据期望的线性性，我们可以把每张牌使用的概率算出来，再把每张牌的期望伤害值相加即可得到答案。
现在问题变成了这个概率怎么求。
设第 \(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;
}