[BZOJ4318] OSU! && [BZOJ3450] Easy

两道都是期望dp,而且套路一样的题,就合成一个blog了。

题意

Easy

n个格子有3个状态0,1,2,2代表各有一半概率是0或1。

求1长度平方和期望。

OSU!

n个格子,给出每个格子为1的概率。

求1长度立方和期望。

思路

Easy中三种格子可以化为0,0.5,1的概率。

所以两个问题的差距只有维护平方和和立方和。

对easy,我们维护最后一段长度d的期望。

长度有p的概率变成d + 1,有(1 - p)的概率变成0,期望可以维护。

答案加上平方和期望的差。

对OSU,再维护长度平方。

Code

Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
char S[300030];
int main()
{
int n;scanf("%d",&n);scanf("%s",S + 1);
double a = 0,f = 0;
for(int i = 1;i <= n;i++)
{
if(S[i] == 'o') a += 2 * f + 1,f += 1;
else if(S[i] == 'x') f = 0;
else a += f + 0.5,f = (f + 1) / 2;
}
printf("%.4lf\n",a);
}

OSU!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Select Code

#include <cstdio>
using namespace std;
int main()
{
int n;scanf("%d",&n);
double ans = 0,Ex = 0,Ex2 = 0,p = 0;
for(int i = 1;i <= n;i++)
{
scanf("%lf",&p);
ans += (3 * Ex2 + 3 * Ex + 1) * p;
Ex2 = (Ex2 + 2 * Ex + 1) * p;
Ex = (Ex + 1) * p;
}
printf("%.1lf\n",ans);
return 0;
}