大型补档计划。
比较显然的dp
设 (f[i][j][k]) 为前 (i) 次,擂台上了 (j) 次,空闲容量(背包 - 使用的)为 (k) 的概率。
-
不上擂台的转移:(f[i + 1][j][k] += f[i][j][k] * (1 - p[i]) / 100)
-
上擂台: (f[i + 1][j + 1][k + a[i]] += f[i][j][k] * p[i] / 100)
看似容量是 (2000),实际上我们需要的不超过 (400),所以可以压缩,不需要的取 (min) 就行。
时间复杂度 (O(n ^ 3))
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 205, S = 405, P = 200;
int n, L, K, a[N];
double p[N], f[N][S], g[N][S];
int main() {
scanf("%d%d%d", &n, &L, &K);
K = min(K, n);
f[0][P + K] = 1;
for (int i = 1; i <= n; i++) scanf("%lf", p + i);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
if (a[i] >= 0) K += a[i];
}
K = min(K, n);
for (int i = 1; i <= n; i++) {
memcpy(g, f, sizeof g);
memset(f, 0, sizeof g);
for (int j = 0; j <= n; j++) {
for (int k = P - n; k <= P + K; k++) {
if (!g[j][k]) continue;
f[j][k] += g[j][k] * (100 - p[i]) / 100;
if (k + a[i] >= 0) {
f[j + 1][min(P + K, k + a[i])] += g[j][k] * p[i] / 100;
}
}
}
}
double ans = 0;
for (int i = L; i <= n; i++)
for (int j = P; j <= P + K; j++) ans += f[i][j];
printf("%.6lf", ans);
return 0;
}