# Luogu p1654 probability DP

2021-01-23 20:17:55

#### 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;
}
``````

https://chowdera.com/2021/01/20210123201637301w.html