「洛谷P1654/BZOJ4318」OSU！

发表于 | 分类于 | | 浏览量： 次

这题代码是真的短，但我就是做不来QwQ…

传送门

洛谷P1654

BZOJ4318

题解

感觉这个期望DP真的挺有趣的。

设$X1_i$表示以$i$为结尾的连续$1$串的期望长度，$X2_i$表示 以$i$为结尾的连续$1$串长度的平方的期望，$F_i$表示$i$次操作后的期望得分。

首先来看看$X1$该怎么递推，第$i$次操作有$Pi$的概率成功，贡献为$X1{i-1}+1$；还有$1-P_i$的概率失败，贡献为$0$，所以

再来看$X2$，根据完全平方公式$(x+1)^2=x^2+2x+1$，同理可得

再根据完全立方公式$(x+1)^3=x^3+3x^2+3x+1$，同理可得

然后$F_n$就是答案 。

然后，然后就…没了。

代码

真的很短哎QwQ。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<cstdio>
using namespace std;
const int maxn=100005;
int n;double P[maxn],X1[maxn],X2[maxn],F[maxn];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf",&P[i]);
		X1[i]=(X1[i-1]+1)*P[i];
		X2[i]=(X2[i-1]+2*X1[i-1]+1)*P[i];
		F[i]=F[i-1]+(3*X2[i-1]+3*X1[i-1]+1)*P[i];
	}
	printf("%.1lf\n",F[n]);
	return 0;
}