比赛 叫图论的DP题 评测结果 AAAAAAAAA
题目名称 组合数 最终得分 100
用户昵称 kZime 运行时间 0.014 s
代码语言 C++ 内存使用 2.24 MiB
提交时间 2017-08-30 21:04:46
显示代码纯文本
  1. # include <cstdio>
  2. # include <algorithm>
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. ll f[51][5023], n, a[51];
  7.  
  8. int main() {
  9. freopen("conbination.in", "r", stdin);
  10. freopen("conbination.out", "w", stdout);
  11. scanf("%d", &n);
  12. int u = n * 100;
  13. ll sum = 0;
  14. f[0][0] = 1;
  15. for(int i = 1; i <= n; i++) {
  16. int a;
  17. scanf("%d", &a);
  18. sum += a;
  19. for(int j = u; ~j; j--) f[i][j] += f[i - 1][j];
  20. for(int j = u - a; ~j; j--) f[i][j + a] += f[i - 1][j];
  21. }
  22. ll cnt = 0, tot = 0;
  23. int l, r;
  24. scanf("%d %d", &l, &r);
  25. for(int i = 0; i <= sum; i++) {
  26. if(i >= l && i <= r) cnt += f[n][i];
  27. tot += f[n][i];
  28. }
  29. printf("%.4lf\n", 1.0 * cnt / tot);
  30. }