比赛 叫图论的DP题 评测结果 AAAAAAAAA
题目名称 组合数 最终得分 100
用户昵称 kZime 运行时间 0.014 s
代码语言 C++ 内存使用 2.24 MiB
提交时间 2017-08-30 21:04:46
显示代码纯文本
# include <cstdio>
# include <algorithm>
using namespace std;
typedef long long ll;

ll f[51][5023], n, a[51];

int main() { 
    freopen("conbination.in", "r", stdin);
    freopen("conbination.out", "w", stdout);
    scanf("%d", &n);
    int u = n * 100;
    ll sum = 0;
    f[0][0] = 1;
    for(int i = 1; i <= n; i++) { 
        int a;
        scanf("%d", &a);
        sum += a;
        for(int j = u; ~j; j--) f[i][j] += f[i - 1][j];
        for(int j = u - a; ~j; j--) f[i][j + a] += f[i - 1][j];
    }
    ll cnt = 0, tot = 0;
    int l, r;
    scanf("%d %d", &l, &r);
    for(int i = 0; i <= sum; i++) { 
        if(i >= l && i <= r) cnt += f[n][i];
        tot += f[n][i];
    }
    printf("%.4lf\n", 1.0 * cnt / tot);
}