ZOJ 8th Anniversary Contest解题报告 » ZOJ3307

ZOJ3307.txt

```#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 218;
bool ok[MAXN];
double dp[MAXN][MAXN];
double a, b, c;

double gao(int l, int r) {
if (l >= r) {
return 0;
} else if (dp[l][r] >= 0) {
return dp[l][r];
} else {
double &ret = dp[l][r];
ret = 0;
for (int i = l; i < r; ++i) {
ret += a * ok[i]  + b * gao(l, i) + c * gao(i + 1, r);
}
ret /= (r - l);
return ret;
}
}

int main() {
int n, k;
int x[MAXN], y[MAXN], z;

while (scanf("%d", &n) != EOF && (n >= 0)) {
for (int i = 0; i < n; ++i) {
scanf("%d", &x[i]);
}
scanf("%d%lf%lf", &k, &a, &b);
c = 1 - (a + b);
copy(x, x + n, y);
sort(y, y + n);
if (k > unique(y, y + n) - y) {
z = -1;
} else {
z = y[k - 1];
}
fill(dp[0], dp[n], -1);
for (int i = 0; i < n; ++i) {
ok[i] = (x[i] == z);
}
printf("%.3lf\n", fabs(gao(0, n)));
}
}
// Run ID       Submit Time     Judge Status    Problem ID      Language  Run Time(ms)          Run Memory(KB)          User Name       Admin
// 1296         2009-07-23 17:58:08     Accepted        1077    C++     1560 552        liehuochongsheng        Source
```