[HNOI2015]亚瑟王

Luogu3239

设第\(i\)张牌被使用的概率为\(f[i]\) , 则\(ans=\sum{f[i]*d[i]}\)
有\(f[1]=1-(1-p[i])^m\)

设\(g[i][j]\)表示前\(i\)张牌中使用\(j\)张的概率 , 则
\[f[i]=\sum{g[i-1][j]*(1-(1-p[i])^{m-j})}\]
即有\(j\)轮不会考虑到\(i\) , 还有\(m-j\)会考虑到\(i\) , 这些轮中又要选\(i\)的概率

转化为求\(g[i][j]\)的转移方程

\(1.\)取了第\(i\)张牌 \(g[i][j]=\sum{g[i-1][j-1]*(1-(1-p[i])^{m-j+1})}\)
\(2.\)没取第\(i\)张牌 \(g[i][j]=\sum{g[i-1][j]*(1-p[i])^{m-j}}\)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
    register LL x=0,f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f*x;
}

const int N=227;
const int M=143;

double g[N][M],pw[N][M],f[N],p[N];
int d[N],n,m;

inline double solve(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        scanf("%lf%d",&p[i],&d[i]);
        f[i]=0,pw[i][0]=1;
        for(int j=0;j<=m;j++) g[i][j]=0;
    }
    if(m==0) return 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) pw[i][j]=pw[i][j-1]*(1.0-p[i]);
    }
    g[1][0]=pw[1][m],g[1][1]=f[1]=1.0-pw[1][m];
    for(int i=2;i<=n;i++){
        for(int j=0;j<=min(i,m);j++){
            if(j) g[i][j]+=g[i-1][j-1]*(1.0-pw[i][m-j+1]);
            if(i!=j) g[i][j]+=g[i-1][j]*pw[i][m-j];
        }
    }
    for(int i=2;i<=n;i++){
        for(int j=0;j<=min(i,m);j++) f[i]+=g[i-1][j]*(1.0-pw[i][m-j]);
    }
    double ans=0;
    for(int i=1;i<=n;i++) ans+=f[i]*d[i];
    return ans;
}

int main(){
    for(int i=read();i;i--) printf("%.10lf\n",solve());
}

[HNOI2015]亚瑟王

原文：https://www.cnblogs.com/lizehon/p/10636498.html