luogu P1654 OSU!

~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

2019寒假集训题

D.OSU!

题面

osu 是一款群众喜闻乐见的休闲软件。

我们可以把osu的规则简化与改编成以下的样子:

一共有n次操作，每次操作只有成功与失败之分，成功对应1，失败对应0，n次操作对应为1个长度为n的01串。在这个串中连续的 X个1可以贡献X^3 的分数，这x个1不能被其他连续的1所包含（也就是极长的一串1，具体见样例解释）

现在给出n，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留1位小数

---

Input

第一行有一个正整数n,表示操作个数。接下去n行每行有一个[0,1]之间的实数，表示每个操作的成功率。

---

Output

只有一个实数，表示答案。答案四舍五入后保留1位小数。

---

Sample Input

3
0.5
0.5
0.5

---

Sample Output

6.0

---

Hint

000分数为0，001分数为1，010分数为1，100分数为1，101分数为2，110分数为8，011分数为8，111分数为27，总和为48，期望为48/8=6.0

$N\leq 10^5$

---

学习$luogu$上$hall_of_history$大佬简洁的题解。

首先，学过数学的幼儿园毕业生都知道$(x+1)^3=x^3+3x^2+3x+1​$

每多增加一个1，则答案就变为原先的$(x+1)^3=x^3+3x^2+3x+1$，

也就是比原先多了$(x+1)^3-x^3=3x^2+3x+1$。

维护这个增加的期望，维护$x_1[i]$表示$x$的期望，维护$x_2[i]$表示$x^2$的期望。

则有$x_1[i]=(x_1[i-1]+1)×p[i]$，$x_2[i]=(x_2[i-1]+2×x_1[i-1]+1)×p[i]$。

所以有： $Ans[i]=Ans[i-1]+(3×x_2[i-1]+3×x_1[i-1]+1)×p[i]$。

我们求$Ans[n]$即可。

Code

#include<bits/stdc++.h>
using namespace std;
long long read()
{
	long long x = 0, w = 0;
	char ch = 0;
	while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return w ? -x : x;
}
const int N = 1e5 + 10;
double p[N], x1[N], x2[N], Ans[N];
long long n;
int main()
{
	n = read();
	for (int i = 1; i <= n; ++i) scanf("%lf", &p[i]);
	for (int i = 1; i <= n; ++i)
	{
		x1[i] = (x1[i - 1] + 1) * p[i];
		x2[i] = (x2[i - 1] + 2 * x1[i - 1] + 1) * p[i];
		Ans[i] = Ans[i - 1] + (3 * x2[i - 1] + 3 * x1[i - 1] + 1) * p[i];
	}
	printf("%.1lf", Ans[n]);
	return 0;
}