题目背景
原 维护队列 参见P1903
题目描述
某一天(WJMZBMR)在打(osu~~~)但是他太弱逼了，有些地方完全靠运气:(
我们来简化一下这个游戏的规则
有(n)次点击要做，成功了就是(`o`)，失败了就是(`x`)，分数是按(combo)计算的，连续(a)个(combo)就有(a imes a)分，(combo)就是极大的连续(`o`)。
比如(`ooxxxxooooxxx`)，分数就是(2 imes 2 + 4 imes 4 = 4) +16=20。
(Sevenkplus)闲的慌就看他打了一盘，有些地方跟运气无关要么是(`o`)要么是(`x`)，有些地方(`o`)或者(`x`)各有(50\%)的可能性，用(`?`)号来表示。
比如(`oo?xx`)就是一个可能的输入。 那么(WJMZBMR)这场(osu)的期望得分是多少呢？
比如(`oo?xx`)的话，(`?`)是(`o`)的话就是(`oooxx` => 9)，是(x)的话就是(`ooxxx` => 4)
期望自然就是((4+9)/2 =6.5)了
输入输出格式
输入格式：
第一行一个整数(n)，表示点击的个数
接下来一个字符串，每个字符都是(`o`,`x`,`?`)中的一个
输出格式：
一行一个浮点数表示答案
四舍五入到小数点后(4)位
如果害怕精度跪建议用(long double)或者(extended)
输入输出样例
输入样例#1：
4
????
输出样例#1：
4.1250
说明
(osu)很好玩的哦
(WJMZBMR)技术还行(雾),(x)基本上很少呢
思路：用dp数组表示期望值，用f数组表示到某位置时连续的o的个数。然后进行分类讨论：
1.当(s[i])为(’o’)时，(dp[i]=dp[i-1]+2×f[i-1]+1,f[i]=f[i-1]+1);
因为((x+1)^2=x^2+2 imes x + 1)
2.当(s[i])为(‘x’)时，(dp[i]=dp[i-1],f[i]=0);
3.(else) 期望和的平均值就好咯，因为概率都是(0.5)，所以都乘(0.5)相加就可以了。
代码：
#include<cstdio>
#include<cstring>
#define dl double
#define maxn 1000007
using namespace std;
int n;
dl dp[maxn],f[maxn];
char s[maxn];
int main() {
scanf("%d%s",&n,s+1);
int len=strlen(s+1);
for(int i=1;i<=len;++i) {
if(s[i]=='x') dp[i]=dp[i-1],f[i]=0;
else if(s[i]=='o') dp[i]=dp[i-1]+2*f[i-1]+1,f[i]=f[i-1]+1;
else dp[i]=dp[i-1]+f[i-1]+0.5,f[i]=(f[i-1]+1)*0.5;
}
printf("%0.4lf
",dp[len]);
return 0;
}