当前位置:网站首页>Luogu p1654 probability DP

Luogu p1654 probability DP

2021-01-23 20:17:55 _ int_ me


Original link

The question

  • In front of us is a length of \(N\) Of 01 Sequence , Location \(a_i\) Yes \(p_i\) Is the probability that 1, Otherwise 0.

  • In sequence , A paragraph is long as \(x\) Continuity of 1 Will bring \(x^3\) Plus points for ( This is all for you 1 The subinterval of can't be replaced by a longer total 1 The interval contains )

  • Expect to score

Ideas

  • consider DP Methods ,\(F_i\) Before presentation i A bit of expectation plus points . And then for the \(i + 1\) position

    • If 0, For the overall bonus, there are 0 contribution

    • We define it as i For the end , whole 1 The expectation of interval length is

      \[E(L_i) \]

    • then , If the first i + 1 Position as 1, The contribution is

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


  • This is because i + 1 Position as 1 when , All with i For the whole ending 1 The interval will be extended to i + 1, So we have to give up this part of our previous contribution , And then add new parts , The final result is a quadratic polynomial

  • Then consider how to calculate \(E(L_i^2)\) and \(E(L_i)\)

    • about \(E(L_i)\), When i + 1 Position as 0 when , obviously \(E(L_{i + 1})\) by 0( After all, it can't be the end of the whole range ),i + 1 Position as 1 when , Obviously there is

    \[\]

    \[ - about $E(L_i^2)$, When i + 1 Position as 0 when , obviously $E(L_{i + 1})$ by 0( The reason as above ),i + 1 Position as 1 when , Yes \]

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

-  All in all, that is to say 

\[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) \]


  • from i + 1 Position as 1 The formula of time contribution to bonus points , Available

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


One side calculation \(F_i\) One side calculation \(E(L_i)\) and $E(l_i^2) $ that will do

AC Code

#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://chowdera.com/2021/01/20210123201637301w.html

随机推荐