BZOJ 4008 亚瑟王

放个链接就好了。。。。。http://blog.csdn.net/popoqqq/article/details/45365759

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define maxv 505
using namespace std;
int t,n,r,d[maxv];
double dp[maxv][maxv],p[maxv];
double f_pow(double x,int y)
{
    double base=x,ans=1.0;
    while (y)
    {
        if (y&1) ans=ans*base;
        base=base*base;
        y>>=1;
    }
    return ans;
}
void work()
{
    scanf("%d%d",&n,&r);
    for (int i=1;i<=n;i++) {scanf("%lf",&p[i]);scanf("%d",&d[i]);}
    memset(dp,0,sizeof(dp));
    dp[0][r]=1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=r;j++)
            dp[i][j]=dp[i-1][j]*f_pow(1-p[i-1],j)+dp[i-1][j+1]*(1-f_pow(1-p[i-1],j+1));
    double ans=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=r;j++)
            ans+=dp[i][j]*(1-f_pow(1-p[i],j))*d[i];
    printf("%.10lf
",ans);
}
int main()
{
    scanf("%d",&t);
    for (int i=1;i<=t;i++) work();
    return 0;
}