luogu P3239 [HNOI2015]亚瑟王

传送门

显然我们可以先算出每种卡牌在整场游戏触发概率,然后乘上权值,加起来就是答案

然而一个卡牌触发了,后面会直接跳过,这个看着很烦

注意到一个卡牌触发概率和自身概率以及前面牌的情况相关(和在哪一轮触发无关).设(f_{i,j})表示整场游戏中前i种牌触发了j种牌的概率,每次转移只要讨论第i种牌是否触发,由于触发一种牌耗费一轮时间,所以一直不触发的概率为((1-p_i)^{r-j}),反之,触发过了的概率为(1-(1-p_i)^{r-j}),所以(f_{i,j}=f_{i-1,j}*(1-p_i)^{r-j}+f_{i-1,j-1}*(1-(1-p_i)^{r-j+1}))

然后计算每种牌触发的概率,也就是(sum_{j=0}^{r-1} f_{i-1,j}*(1-(1-p_i)^{r-j}))

#include<bits/stdc++.h>
#define LL long long
#define db double
#define il inline
#define re register

using namespace std;
const int N=233;
il int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
int n,m;
db p[N],d[N],f[N][N];

int main()
{
    int T=rd();
    while(T--)
    {
        memset(f,0,sizeof(f));
        n=rd(),m=rd();
        for(int i=1;i<=n;++i) scanf("%lf%lf",&p[i],&d[i]);
        memset(f,0,sizeof(f));
        f[0][0]=1;
        for(int i=1;i<=n;++i)
            for(int j=0;j<=m;++j)
                f[i][j]=f[i-1][j]*pow(1-p[i],m-j)+(j?f[i-1][j-1]*(1-pow(1-p[i],m-j+1)):0);
        db ans=0;
        for(int i=1;i<=n;++i)
            for(int j=0;j<m;++j)
                ans+=d[i]*f[i-1][j]*(1-pow(1-p[i],m-j));
        printf("%.10lf
",ans);
    }
    return 0;
}