【BZOJ 4318】OSU!

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4318
神犇题解:https://oi.men.ci/bzoj-4318/

解题报告

设$p_i$为第$i$个操作成功的概率
设$E_{(i,x^3)}$为以第$i$个位置为结尾,$($极长$1$的长度$x)^3$的期望
$E_{(i,x^2)},E_{(i,x)}$分别表示$x^2,x$的期望

那么根据全期望公式,我们有如下结论:

$E_{(i,x^3)}=p_i \times E_{(i-1,(x+1)^3)}$
$E_{(i,x^2)}=p_i \times E_{(i-1,(x+1)^2)}$
$E_{(i,x)}=p_i \times (E_{(i-1,x)} + 1)$

不难发现只有第三个式子可以直接算
但我们还知道一个东西叫期望的线性,于是我们可以将前两个式子化为:

$E_{(i,x^3)}=p_i \times (E_{(i-1,x^3)} + 3E_{(i-1,x^2)} + 3E_{(i-1,x)} + 1)$
$E_{(i,x^2)}=p_i \times (E_{(i-1,x^2)} + 2E_{(i-1,x)} + 1)$

然后就可以直接维护,然后再根据期望的线性加入答案就可以辣!
时间复杂度:$O(n)$

另外,似乎直接算贡献也可以?
可以参考:http://blog.csdn.net/PoPoQQQ/article/details/49512533

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	int n=read(); 
	double e1=0,e2=0,e3=0,ans=0,p;
	for (int i=1;i<=n;i++) {
		scanf("%lf",&p);
		ans += e3 * (1 - p);
		e3 = p * (e3 + 3 * e2 + 3 * e1 + 1);
		e2 = p * (e2 + 2 * e1 + 1);
		e1 = p * (e1 + 1);
	} 
	printf("%.1lf\n",ans+e3);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注