比赛 |
动态规划练习 |
评测结果 |
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();