题目大意
「Codeforces 464D」World of Darkraft - 2
有 $k$ 种装备，初始等级为 $1$（等级为整数）。共有 $n$ 只怪兽，每杀掉一只后会随机掉落一种装备。假设玩家的那件装备的等级为 $l$，则掉落的新装备的等级会在 $[1, l + 1]$ 中均匀随机。拿到装备后，玩家会保留更好的装备，并把相对差的装备卖掉，获得装备等级的收益。问期望收益。
数据范围：$n \le 10^5, k \le 200$，答案与标准答案绝对或相对误差不超过 $10^{-9}$ 即可。
思路分析
首先发现 $k$ 个装备是独立的，我们只需考虑一件装备即可。
令 $dp(i, j)$ 表示打完第 $i$ 只怪，装备等级为 $j$ 的概率。
考虑从 $dp(i)$ 转移到 $dp(i + 1)$。有两种情况：第一种是恰好随机到该装备，并且恰好随机到更高的等级。这样等级会增加一，概率为 $\frac{1}{k \times (j + 1)}$。第二种是其他情况，等级不会发生改变。
在更新 DP 的过程中，我们计算对答案的贡献。如果当前等级为 $j$，则打完一个怪后期望得到：
的收益。直接计算即可。
现在我们已经得到了 $O(n ^ 2)$ 的算法，但是它还不够优秀。我们考虑从题目入手，发现答案与标准答案绝对或相对误差不超过 $10^{-9}$ 即可通过本题。又发现 $dp(i, j)$ 在 $j$ 很大的时候几乎为 $0$。
于是我们设定阈值 $m = 800$，只计算 $j \le m$ 的 DP 值即可。时间复杂度 $O(nm)$。
听说 $m = O(\sqrt{n})$？看来我还是太菜了。
代码实现
1 | |
2 | |
3 | using namespace std; |
4 | |
5 | typedef long double db; |
6 | const int maxn = 1e5, maxm = 800; |
7 | int n, m, k; |
8 | db inv[maxm + 3], dp[2][maxm + 3], ans; |
9 | |
10 | int main() { |
11 | scanf("%d %d", &n, &k); |
12 | m = min(n + 1, maxm); |
13 | for (int i = 1; i <= maxm + 1; i++) { |
14 | inv[i] = (db) 1 / i; |
15 | } |
16 | int cur = 0, nxt = 1; |
17 | dp[cur][1] = 1; |
18 | for (int i = 0; i < n; i++) { |
19 | for (int j = 1; j <= m; j++) { |
20 | dp[nxt][j] = 0; |
21 | } |
22 | for (int j = 1; j <= m; j++) { |
23 | db x = inv[k] * inv[j + 1]; |
24 | dp[nxt][j] += dp[cur][j] * (1 - x); |
25 | dp[nxt][j + 1] += dp[cur][j] * x; |
26 | ans += dp[cur][j] * ((j + 1) * (j + 2) / 2 - 1) * inv[j + 1]; |
27 | } |
28 | swap(cur, nxt); |
29 | } |
30 | double res = ans; |
31 | printf("%.18lf\n", res); |
32 | return 0; |
33 | } |