比赛 |
叫图论的DP题 |
评测结果 |
RRRRRRRRRR |
题目名称 |
采药 |
最终得分 |
0 |
用户昵称 |
bear |
运行时间 |
0.004 s |
代码语言 |
C++ |
内存使用 |
0.35 MiB |
提交时间 |
2017-08-30 16:17:19 |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <string>
#include <cstring>
#include <sstream>
#include <cmath>
#include <limits>
#include <algorithm>
#include <iterator>
#include <memory.h>
#include <time.h>
using namespace std;
#define CUR_NAMESPACE namespace conbination {
CUR_NAMESPACE
const int N = 50;
const int C = 4505;
typedef unsigned long long ULL;
class Solver
{
private:
int n;
int arr[N];
ULL dp[C];
public:
void Solve()
{
scanf("%d", &n);
int c = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
c += arr[i];
}
for (int i = 0; i <= n; i++) dp[0] = 1;
dp[arr[1]] = 1;
for (int i = 2; i <= n; i++) {
for (int j = c; j >= arr[i]; j--) {
dp[j] += dp[j - arr[i]];
}
}
double denom = 0.0;
for (int i = 0; i <= c; i++) {
denom += dp[i];
}
int l, r;
scanf("%d%d", &l, &r);
double nom = 0.0;
for (int i = l; i <= r; i++) {
nom += dp[i];
}
printf("%.4f", nom / denom);
}
} solver;
void Launch()
{
solver.Solve();
}
#define NAMESPACE_END }
NAMESPACE_END
int main()
{
freopen("conbination.in", "r", stdin);
freopen("conbination.out", "w+", stdout);
conbination::Launch();
return 0;
}