当前位置:网站首页>Luogu P1654 概率DP

Luogu P1654 概率DP

2021-01-23 20:17:09 _int_me


原题链接

题意

  • 我们面前有一个长度为\(N\)的01序列,位置 \(a_i\)\(p_i\) 的概率是1,否则为0。

  • 序列中,一段长为 \(x\) 的连续1会带来 \(x^3\) 的加分(这段全为1的子区间不能被更长的全1区间包含)

  • 求得分期望

思路

  • 考虑DP的方法,\(F_i\) 表示前i位的期望加分。然后对于第 \(i + 1\)

    • 如果为0,则对于总体加分有0贡献

    • 我们定义以i为结尾,全1区间长度的期望是

      \[E(L_i) \]

    • 然后,如果第i + 1位为1,则贡献为

      \[E((L_i + 1)^3) - E(L_i^3) = 3 * E(L_i^2) + 3 * E(L_i) + 1 \]


  • 这是因为i + 1位为1时,所有以i为结尾的全1区间都会延长至i + 1,从而我们必须要放弃之前的这部分贡献,然后加上新的部分,最终得到的是一个二次多项式

  • 然后考虑如何计算 \(E(L_i^2)\)\(E(L_i)\)

    • 对于 \(E(L_i)\), 当i + 1位为0时,显然 \(E(L_{i + 1})\) 为0(毕竟不可能成为全一区间结尾了),i + 1位为1时,显然有

    \[\]

    \[ - 对于 $E(L_i^2)$, 当i + 1位为0时,显然 $E(L_{i + 1})$ 为0(原因同上),i + 1位为1时,有 \]

E(L_{i + 1}^2) = E((L_i + 1)^2) = E(L_i^2) + 2 * E(L_i) + 1
$$

- 总起来也就是说

\[E(L_{i + 1}) = p_{i + 1} * (E(L_i) + 1) \\ E(L_{i + 1}^2) = p_{i + 1} * E((L_i + 1)^2) = p_{i + 1} * (E(L_i^2) + 2 * E(L_i) + 1) \]


  • 由i + 1位为1时对加分贡献的式子,可得

\[ F_{i + 1} = F_i + p_{i + 1} * (3 * E(L_i^2) + 3 * E(L_i) + 1) \]


一边计算 \(F_i\) 一边计算 \(E(L_i)\) 和 $E(l_i^2) $即可

AC代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int n;
double p;

int main()
{
	scanf("%d", &n);
	double acc = 0;
	double x2 = 0, x = 0;
	for (int i = 0; i < n; ++i)
	{
		scanf("%lf", &p);
		acc += p * (3 * x2 + 3 * x + 1);
		x2 = p * (x2 + 2 * x + 1);
		x = p * (x + 1);
	}
	printf("%.1f", acc);
	return 0;
}

版权声明
本文为[_int_me]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/int-me-X/p/14318772.html

随机推荐