记录编号	538549	评测结果	AAAAAAAAAA
题目名称	[HNOI 2015]亚瑟王	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.771 s
提交时间	2019-07-26 14:44:23	内存使用	14.49 MiB

#include<bits/stdc++.h>
#define db double
const int N=233;
db dp[N][N],p[N],q[N][N];//q[i][j]表示(1-p[i])^j
int d[N];
int T,n,r;
int main()
{
    freopen("arthur.in","r",stdin);
	freopen("arthur.out","w",stdout);
	scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&r);
        for(int i=1;i<=n;++i)
        {
            scanf("%lf%d",&p[i],&d[i]);
            q[i][0]=1;
            for(int j=1;j<=r;++j)  q[i][j]=q[i][j-1]*(1-p[i]);
        }
        dp[0][0]=1;
        for(int i=1;i<=n;++i)for(int j=0;j<=i&&j<=r;++j)
        {
            dp[i][j]=j?dp[i-1][j-1]*(1-q[i][r-j+1]):0;
            dp[i][j]+=dp[i-1][j]*q[i][r-j];
        }
        db ans=0;
        for(int i=1;i<=n;++i) for(int j=0;j<i&&j<r;++j)
        ans+=d[i]*(dp[i-1][j]*(1-q[i][r-j]));
        printf("%.10lf\n",ans);
    }
    return 0;
}