题目大意
有一个长度为 $n$ 的 $01$ 串，第 $i$ 位有 $p_i$ 的概率为 $1$，有 $1 - p_i$ 的概率为 $0$。每一段长度为 $x$ 的极长的 $1$ 对得分有 $x^3$ 的贡献。问期望得分。
数据范围：$n \le 10^5$。
思路分析
考虑第 $i$ 位把答案增加了多少。如果它为 $0$，则没有贡献，否则它的贡献为：$(x + 1) - x ^ 3 = 3 x ^ 2 + 3 x + 1$，其中 $x$ 是第 $i - 1$ 为往前的最长的一段 $1$。于是，我们成功的把三次的问题降成了两次。
接下来考虑维护第 $i$ 位往前的最长连续 $1$ 的期望长度的平方。同样地，发现 $(x + 1) ^ 2 - x ^ 2 = 2 x + 1$，于是我们把二次问题降成了一次。
最后考虑维护第 $i$ 位往前的最长连续 $1$ 的期望长度。同样是分 $0, 1$ 讨论，容易得出递推公式。具体实现见代码。
时间复杂度：$O(n)$。
代码实现
1 | |
2 | |
3 | typedef double db; |
4 | const int maxn = 1e5; |
5 | int n; |
6 | db x, dp[maxn + 3][3]; |
7 | |
8 | int main() { |
9 | scanf("%d", &n); |
10 | for (int i = 1; i <= n; i++) { |
11 | scanf("%lf", &x); |
12 | dp[i][0] = (dp[i - 1][0] + 1) * x; |
13 | dp[i][1] = (dp[i - 1][1] + dp[i - 1][0] * 2 + 1) * x; |
14 | dp[i][2] = dp[i - 1][2] + (dp[i - 1][1] * 3 + dp[i - 1][0] * 3 + 1) * x; |
15 | } |
16 | printf("%.1lf\n", dp[n][2]); |
17 | return 0; |
18 | } |