比赛 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;
}