题目描述
你有一个容量为 $m$(题目中为 $k$,但为了后面 dp
变量方便解释,所以改成 $m$) 的背包,现在有 $n$ 个游戏,每个游戏有 $p_i$ 的概率获胜,获胜时,背包容量会增加 $a_i$($a_i \in [-1, \ 200]$ 且 $a_i \not= 0$)。
对这 $n$ 个游戏,求至少赢 $l$ 个游戏,背包容量仍 $\geqslant 0$ 的概率。
输入方式为:
-
第一行 $n, \ l, \ m$
-
第二行 $n$ 个整数,代表 $p_i \times 100$($1 \leqslant i \leqslant n$)
-
第三行 $n$ 个整数,代表 $a_i$($1 \leqslant i \leqslant n$)
样例
Input1
3 1 0
10 20 30
-1 -1 2
Output1
0.300000000000
Input2
1 1 1
100
123
Output2
1.000000000000
概率 dp
$f[i][j][k]$ 表示表示前 $i$ 个游戏,赢了 $j$ 个,背包容量还剩 $k$ 的概率。
若按照题目所给 $a_i$ 的顺序,有可能出现背包容量先变为负数,再增加至非负数的情况,这样转移更麻烦,还需要偏移量,因此把 $a$ 降序排序,这样所有 $-1$ 都排在后面,就可以保证只有 $k + a[i] \geqslant 0$ 时才能转移;同时,$k + a[i]$ 只要达到 $n$ 及以上,就都按照 $n$ 算,因为总共就 $n$ 个游戏,最多 $-n$。
状态转移:
-
第 $i$ 个游戏没赢:$f[i][j][k] = f[i - 1][j][k] \times (1 - p[i])$
-
第 $i$ 个游戏赢了:
-
$a[i] \gt 0$:$f[i][j + 1][\min(n, \ k + a[i])] = f[i - 1][j][k] \times p[i]$
-
$a[i] = -1$:$f[i][j + 1][k - 1] = f[i - 1][j][k] \times p[i]$,当且仅当 $k \gt 0$
-
边界条件:$f[0][0][\min(n, \ m)] = 1$,表示未开始游戏时的背包容量为 $m$。
答案:$\sum\limits_{i = l}^{n}{\sum\limits_{j = 0}^{n}{f[n][i][j]}}$(至少赢 $l$ 个游戏)。
时间复杂度 $O(n^3)$
空间复杂度 $O(n^2)$
由于第 $i$ 维只和第 $i - 1$ 维有关,因此可以用滚动数组将空间复杂度减少一个 $n$ 的量级
C++ 代码
#include <bits/stdc++.h>
using LL = long long;
struct Node {
int a;
double p;
constexpr Node(): a{}, p{} {}
constexpr Node(int _a, int _p): a{_a}, p{_p / 100.0} {}
friend constexpr bool operator<(Node lhs, Node rhs) {
return lhs.a > rhs.a;
}
};
void solve() {
int n, l, m;
std::cin >> n >> l >> m;
std::vector<Node> b(n);
for (int i = 0; i < n; i += 1) {
std::cin >> b[i].p;
b[i].p /= 100;
}
for (int i = 0; i < n; i += 1) {
std::cin >> b[i].a;
}
std::sort(b.begin(), b.end());
std::vector f(n + 1, std::vector<double>(n + 1));
f[0][std::min(n, m)] = 1;
for (int i = 0; i < n; i += 1) {
auto g = f;
for (int j = 0; j <= n; j += 1) {
g[j].assign(n + 1, 0);
}
for (int j = 0; j <= i; j += 1) {
for (int k = 0; k <= n; k += 1) {
if (b[i].a == -1) {
if (k > 0) {
g[j + 1][k - 1] += f[j][k] * b[i].p;
}
} else {
int t = std::min(n, k + b[i].a);
g[j + 1][t] += f[j][k] * b[i].p;
}
g[j][k] += f[j][k] * (1 - b[i].p);
}
}
f.swap(g);
}
double ans = 0;
for (int i = l; i <= n; i += 1) {
for (int j = 0; j <= n; j += 1) {
ans += f[i][j];
}
}
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(12);
int T = 1;
// std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}