比赛 |
2024暑假C班集训D |
评测结果 |
AWWWWWEWWE |
题目名称 |
亚瑟王 |
最终得分 |
10 |
用户昵称 |
dream |
运行时间 |
0.921 s |
代码语言 |
C++ |
内存使用 |
3.55 MiB |
提交时间 |
2024-07-13 11:56:10 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=500;
int n,r;
double a[N];
int d[N];
double sum[N];
double sh[N];
int mk[N];
int cnt;
void dfs(int l,double gl,int s){
if(l>r){
sum[++cnt]=gl;
sh[cnt]=s;
// cout<<gl<<" "<<s<<"\n";
return;
}
double q=1;
for(int i=1;i<=n;i++){
if(!mk[i])
q*=1.0-a[i];
}
dfs(l+1,gl*q,s);
for(int i=1;i<=n;i++){
if(!mk[i]){
double w=1;
for(int j=1;j<i;j++){
if(!mk[j])
w*=1.0-a[j];
}
mk[i]=1;
// cout<<l<<"-------";
// cout<<gl<<" "<<w<<" "<<a[i]<<"\n";
dfs(l+1,gl*w*a[i],s+d[i]);
mk[i]=0;
}
}
}
int main(){
freopen("arthur.in","r",stdin);
freopen("arthur.out","w",stdout);
int t;
cin>>t;
while(t--){
cnt=0;
memset(mk,0,sizeof(mk));
cin>>n>>r;
for(int i=1;i<=n;i++){
cin>>a[i]>>d[i];
}
dfs(1,1,0);
double ans=0;
for(int i=1;i<=cnt;i++){
ans+=sum[i]*sh[i];
}
printf("%.10f\n",ans);
}
return 0;
}