比赛 2024暑假C班集训D 评测结果 ATTTTTTTTT
题目名称 亚瑟王 最终得分 10
用户昵称 彭欣越 运行时间 26.990 s
代码语言 C++ 内存使用 3.70 MiB
提交时间 2024-07-13 11:53:34
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
int t,n,r,mk[100010];
double res;
struct node {
    double s;
    int x;
}a[250];
void dfs (int idx,double ans,int k) {
    if (idx>r) {
        //cout << ans <<' '<< k <<endl;
        res+=ans*k;
        return;
    }
    double cnt=1;
    for (int i=1;i<=n;i++) {
        if (mk[i]) continue;
        mk[i]=1;
        dfs(idx+1,ans*cnt*a[i].s,k+a[i].x);
        mk[i]=0;
        cnt*=(1-a[i].s);
    }
    dfs(idx+1,cnt*ans,k);
}
int main () {
    freopen("arthur.in","r",stdin);
    freopen("arthur.out","w",stdout);
    cin >> t;
    while (t--) {
        res=0;
        memset(mk,0,sizeof(mk));
        cin >> n >> r;
        for (int i=1;i<=n;i++) {
            cin >> a[i].s >> a[i].x;
        }
        dfs(1,1,0);
        printf("%.10f",res);
    }
    return 0;
}