CF1810G 题解
EuphoricStar
·
·
题解
感觉是比较 educational 的题。
拿到题目应该有一个大致思路，就是考虑最大前缀和的求法，再把它扔到状态里面。
最大前缀和有两种求法：
- 从前往后求，需要维护当前前缀和 s，当前最大前缀和 mx，需要记录两个变量，无法承受。
- 从后往前求，只需记录当前最大前缀和 mx，从 [i + 1, n] 的最大前缀和转移到 [i, n] 的最大前缀和时，我们贪心地判断 a_i 是否属于最大前缀和，即 mx \gets \max(mx + a_i, 0)。
于是我们有一个初步的 dp 思路：设 f_{i, j} 为当前考虑了 [i, n]，其最大前缀和为 j。有转移：
\begin{cases} p_i f_{i + 1, j} \to f_{i, j + 1} \\ (1 - p_i) f_{i + 1, j} \to f_{i, \max(j - 1, 0)} \end{cases}
初值为 f_{n + 1, 0} = 1，最终 ans = \sum\limits_{i = 0}^n h_i f_{1, i}。
我们算的只是长度为 n 的答案，我们希望对于每个长度 l 都求出答案，但是直接做是 O(n^3) 的。
注意到我们每次 dp 的转移都是固定的，只是初值不同（长度为 l 时 dp 初值为 f_{l + 1, 0} = 1），因此 f_{i, j} 对答案的贡献也是固定的。我们不妨使用反推贡献系数的 trick，设 g_{i, j} 为 f_{i, j} 对 ans 的贡献系数，那么有转移：
g_{i + 1, j} = p_i g_{i, j + 1} + (1 - p_i) g_{i, \max(j - 1, 0)}
初值为 g_{1, i} = h_i。最终长度为 l 的答案为 g_{l + 1, 0}。
时间复杂度降至 O(n^2)。
code