比赛 2024暑假C班集训D 评测结果 ATTTTTTTTT
题目名称 亚瑟王 最终得分 10
用户昵称 wzh0425 运行时间 26.993 s
代码语言 C++ 内存使用 3.39 MiB
提交时间 2024-07-13 09:55:57
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int T,n,r,vis[505],d[505];
double p[505],ans;
void dfs(int cs,double gl,int gjl){
    if (cs>=r){
        //cout<<gl<<" "<<gjl<<endl;
        ans+=gl*gjl*1.0;
        return;
    }
    double rpl=1-gl,pl;
    for (int i=1;i<=n+1;i++){
        if (i==n+1){
            pl=(1-rpl)*1;
            rpl=rpl+pl;
            dfs(cs+1,pl,gjl);
        }else{
            if (vis[i]==0){
                pl=(1-rpl)*p[i];
                rpl=rpl+pl;
                //cout<<i<<" "<<pl<<endl;
                vis[i]=1;
                dfs(cs+1,pl,gjl+d[i]);
                vis[i]=0;
            }
        }
    }
}
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++){
            cin>>p[i]>>d[i];
        }
        //cout<<p[1]<<endl;
        dfs(0,1.0,0);
        printf("%.10f\n",ans);
    }
    return 0;
}