1 条题解
-
-1曾致瑜 (zengzhiyu) LV 6 @ 2023-1-31 22:13:18
#include <bits/stdc++.h> #define maxn 210 using namespace std; int n, L, K, s, a[maxn]; double p[maxn], dp[2][maxn][maxn << 1], ans; inline int read(){ int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } int main(){ n = read(), L = read(), K = read(); s = K; for (int i = 1; i <= n; ++i) p[i] = 1.0 * read() / 100; for (int i = 1; i <= n; ++i) s += max(0, a[i] = read()); dp[0][0][n + K] = 1; s = n; for (int i = 1; i <= n; ++i){ int now = i & 1, pre = now ^ 1; for (int j = 0; j <= i; ++j) for (int k = 0; k <= n + s; ++k) dp[now][j][k] = 0; for (int j = 0; j <= i - 1; ++j){ for (int k = 0; k < n + s; ++k) if (dp[pre][j][k] > 0){ dp[now][j][k] += dp[pre][j][k] * (1.0 - p[i]); if (k + a[i] >= 0 && k + a[i] < n + s) dp[now][j + 1][k + a[i]] += dp[pre][j][k] * p[i]; } } } int now = n & 1; for (int i = n; i < n + s; ++i) for (int j = L; j <= n; ++j) ans += dp[now][j][i]; memset(dp, 0, sizeof(dp)); dp[0][0][n + K] = 1; for (int i = 1; i <= n; ++i){ int now = i & 1, pre = now ^ 1; for (int j = 0; j <= i; ++j) for (int k = 0; k <= n + s; ++k) dp[now][j][k] = 0; for (int j = 0; j <= i - 1; ++j) for (int k = 0; k <= n + s; ++k) if (dp[pre][j][k] > 0){ dp[now][j][k] += dp[pre][j][k] * (1.0 - p[i]); if (k + a[i] >= n + s || k >= n + s) dp[now][j + 1][n + s] += dp[pre][j][k] * p[i]; else if (k + a[i] < n + s && k + a[i] >= 0) dp[now][j + 1][k + a[i]] += dp[pre][j][k] * p[i]; } } now = n & 1; for (int i = L; i <= n; ++i) ans += dp[now][i][n + s]; printf("%.6lf\n", ans); return 0; }
代码不好看,请各位大佬将就一下
- 1
信息
- ID
- 143
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 5
- 标签
- 递交数
- 15
- 已通过
- 14
- 上传者