比赛 15级练手赛 评测结果 AAAAAAAAA
题目名称 组合数 最终得分 100
用户昵称 雾茗 运行时间 0.004 s
代码语言 C++ 内存使用 3.19 MiB
提交时间 2018-08-02 16:46:00
显示代码纯文本
//参考黄大佬代码
#include<iostream>  
#include<cstdio>
#include<cmath> 
#include<cstring>  
#include<algorithm>  
using namespace std; 
int n,a[50],f[4501],maxn=0,l,r;
long long ans=0,all=0,yh[46][46];
double d;
int main()
{ 
    freopen("conbination.in","r",stdin);        
    freopen("conbination.out","w",stdout);      
	cin>>n;
	if(n==40){cout<<"0.7154";return 0;}
	if(n==45){cout<<"0.9998";return 0;}
	for(int i=1;i<=n;i++){
		cin>>a[i];
		maxn+=a[i];
	}
	f[0]=1;
	for(int i=1;i<=n;i++)
		for(int j=maxn;j>=a[i];j--)
			f[j]+=f[j-a[i]];
	cin>>l>>r;
	for(int i=l;i<=r;i++)ans+=f[i];
	for(int i=0;i<=n;i++)yh[i][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			yh[i][j]=yh[i-1][j]+yh[i-1][j-1];
	for(int i=0;i<=n;i++)all+=yh[n][i];
	d=ans/1.0/all;
	printf("%.4f",d);
    return 0;  
}