比赛 2024暑假C班集训D 评测结果 ATTTTTTTTT
题目名称 亚瑟王 最终得分 10
用户昵称 Untitled 运行时间 26.987 s
代码语言 C++ 内存使用 3.31 MiB
提交时间 2024-07-13 10:11:02
显示代码纯文本
#include <bits/stdc++.h> 
using namespace std;

int t,n,r,h[230];
double res,p[230];
bool d[230];

void dfs(int x,int k,double v,int w){
    double non=1;
    for (int i=1;i<=n;i++) if (!d[i]) non*=1-p[i];
    if (k==r){
        res+=v*w;
        return;
    }
    d[x]=1;
    double g=1.0;
    for (int i=1;i<=n;i++){
        if (d[i]) continue;
        dfs(i,k+1,v*p[i]*g,w+h[i]);
        g*=(1.0-p[i]);
    }
    dfs(0,k+1,v*g,w);
    d[x]=0;
    return;
}

int main(){
    freopen("arthur.in","r",stdin);
    freopen("arthur.out","w",stdout);
    
    double a;
    cin>>t;
    for (int x=1;x<=t;x++){
        cin>>n>>r;
        for (int i=1;i<=n;i++){
            cin>>p[i]>>h[i];
        }
        res=0.0;
        dfs(0,0,1,0);
        printf("%.12f\n",res);
    }
    
    return 0;
}