-
先考虑一个 \(O(n^2)\) 的 dp
-
设计状态： \(dp_i\) 表示搭 \(i\) 层的期望
-
转移：\(dp_i=dp_{i-1}\times(1-P_i)+\sum\limits_{j=i}^{n-1}dp_j\times P_{j+1}^{j-i+1} \times (1-P_{j+1})\) ，显然是有后效性的，但我们展开 \(dp_{n}\) ，移一下项，就变成了之和 \(dp_{n-1}\) 有关的了，就这样一直展开到 \(dp_0\) 再递推回去，就可以做到 \(O(n^2)\)
-
-
考虑优化，我们的复杂度主要在哪？主要是在后面部分的展开，换言之我们并不好考虑从高层掉到第 \(i\) 层的情况，因此我们不妨考虑强制从 \(i-1 \rightarrow i\) 的期望
-
设计状态： \(dp_i\) 表示从 \(i-1 \rightarrow i\) 的期望次数
-
转移：
-
\[\begin{align} dp_i &=1+\sum_{j=1}^{i}dp_j\times P_i^i + \sum_{j=1}^{i-1} P_i^j \times (1-P_i) \times \sum_{k=i-j+1}^{i} dp_k \\ &=1+\sum_{j=1}^{i}dp_j\times P_i^i + \sum_{k=1}^{i} \sum_{j=i-k+1}^{i-1} P_i^j \times (1-P_i) \times dp_k \\ &=1+\sum_{j=1}^{i}dp_j\times P_i^i + \sum_{k=1}^{i} \sum_{j=i-k+1}^{i-1} P_i^j \times (1-P_i) \times dp_k \\ &=1+\sum_{j=1}^{i}dp_j\times P_i^i + \sum_{k=1}^{i} (P_i^{i-k+1}-P_i^i)\times dp_k \\ &=1+\sum_{j=1}^{i}dp_j\times P_i^{i-j+1}\\ (1-P_i)dp_i &=1+\sum_{j=1}^{i-1} dp_j\times P_i^{i-k+1}\\ dp_i &=\frac{1+\sum_{j=1}^{i-1} dp_j\times P_i^{i-k+1}}{i-P_i} \end{align} \]
-
优化转移：发现 \(P_i\) 的原因并不好优化，但原题 \(P_i \leq 99\) ，因此我们可以直接对每一种 \(P_i\) 都做一遍前缀和，最终复杂度 \(O(n \Sigma)\)
-
CF1866M Mighty Rock Tower 题解
发布时间 2023-11-03 19:18:26作者: FOX_konata