比赛 2024暑假C班集训D 评测结果 ATTTTTEEEE
题目名称 亚瑟王 最终得分 10
用户昵称 djyqjy 运行时间 15.824 s
代码语言 C++ 内存使用 3.30 MiB
提交时间 2024-07-13 11:52:02
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int mark[N];
int t;
int n,r;
struct kp
{
    double p;
    int d;
}ks[N];
double ans;
void dfs(int c,int s,double g)
{
    if(c>r)
    {
        ans+=s*g;
        return;
    }
    double gp=g;
    for(int i=1;i<=n;i++)
    {
        if(mark[i]==1) continue;
        mark[i]=1;
        dfs(c+1,s+ks[i].d,gp*ks[i].p);
        mark[i]=0;
        gp*=1-ks[i].p;
    }
    dfs(c+1,s,gp);
    return;
}
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",&ks[i].p,&ks[i].d);
        }
        dfs(1,0,1);
        printf("%.10lf",ans);
        memset(mark,0,sizeof(mark));
        ans=0;
    }
    return 0;
}