比赛 动态规划练习 评测结果 AAAAAAAAA
题目名称 组合数 最终得分 100
用户昵称 TARDIS 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2017-03-26 19:14:00
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<deque>
#define maxn 50
#define maxa 101
#define itn int
#define xlm mylove
using namespace std;
typedef long long LL;typedef unsigned long long ULL;
LL n,a[maxn],sum[maxn],l,r;LL f[maxn][maxn*maxa];
LL all=1,get=0;double ans;
inline void in(){
//	freopen("a.in","r",stdin);
	freopen("conbination.in","r",stdin);
	freopen("conbination.out","w",stdout);
	scanf("%lld",&n);
	for (int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	scanf("%lld%lld",&l,&r);
}
inline void dp(){
//	LL sumget=sum[n];
	for (int i=1;i<=n;i++){
		f[i][a[i]]=1;
		for (int j=1;j<=sum[i];j++){
			if (j<a[i]) f[i][j]+=f[i-1][j];
			else f[i][j]+=f[i-1][j]+f[i-1][j-a[i]];
		}
	}
}
inline void p(){
	for (int i=0;i<=sum[n];i++){
		if (i>=l&&i<=r) get+=f[n][i];
		all+=f[n][i];
	}
	if (l==0) get++;
	ans=(double)get/(double)all;
//	printf("%lld %lld\n",get,all);
	printf("%.4f",ans);
}
int Main(){
	in();
	dp();
	p();
	return 0;
}
int main(){;}
int xlm=Main();