比赛 2024暑假C班集训D 评测结果 ATTTTTTTTT
题目名称 亚瑟王 最终得分 10
用户昵称 123 运行时间 26.990 s
代码语言 C++ 内存使用 6.91 MiB
提交时间 2024-07-13 11:51:25
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=220;
double p[N],ret=0;
int t,n,m,d[N],flag[N];
void dfs(int step1,int step2,int k,double cnt)
{
    if (step2==m+1)
    {
        ret+=k*cnt;
        return ;
    }
    if (step1==n+1)
    {
        dfs(1,step2+1,k,cnt);
        return ;
    }
    if (flag[step1])
    {
        dfs(step1+1,step2,k,cnt);
    }
    else
    {
        dfs(step1+1,step2,k,cnt*(1-p[step1]));
    }
    if (!flag[step1])
    {
        flag[step1]=1;
        dfs(1,step2+1,k+d[step1],cnt*p[step1]);
        flag[step1]=0;
    }
}
int main() {
    freopen("arthur.in","r",stdin);
    freopen("arthur.out","w",stdout);
    scanf("%d",&t);
    while (t--)
    {
        ret=0;
        memset(flag,0,sizeof(flag));
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
        {
            scanf("%lf%d",&p[i],&d[i]);
        }
        dfs(1,1,0,1);
        printf("%.10f",ret);
    }
}