BZOJ3450. Tyvj1952 Easy（期望dp）

本文主要是介绍BZOJ3450. Tyvj1952 Easy（期望dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
某一天WJMZBMR在打osu~~~但是他太弱逼了，有些地方完全靠运气:(
我们来简化一下这个游戏的规则
有n次点击要做，成功了就是o，失败了就是x，分数是按comb计算的，连续a个comb就有aa分，comb就是极大的连续o。
比如ooxxxxooooxxx，分数就是22+4*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了

Input

第一行一个整数n，表示点击的个数
接下来一个字符串，每个字符都是ox？中的一个

Output
一行一个浮点数表示答案
四舍五入到小数点后4位
如果害怕精度跪建议用long double或者extended

Sample Input
4
???
Sample Output
4.1250

n<=300000
osu很好玩的哦
WJMZBMR技术还行(雾),x基本上很少呢
Hint
Source
我们都爱GYZ杯

思路：
维护后缀最长$o$ ，数目为l。
令f[i]为到了第i个字符的获得值。

$s[i]{=}^{\prime }{o}^{\prime }f[i]=f[i-1]+l\ast 2+1,l++$
$PS：(l+1)\ast (l+1)-l\ast l=l\ast 2+1$
$s[i]{=}^{\prime }{x}^{\prime }f[i]=f[i-1]$
$s[i]{=}^{\prime }{?}^{\prime }f[i]=(f[i-1]+l\ast 2+1)\ast 0.5,l=(l+1)\ast 0.5$

f[i]可以用一个变量代替。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 3e5 + 7;double f[maxn];
char s[maxn];int main()
{int n;scanf("%d",&n);scanf("%s",s + 1);double l = 0,ans = 0.0;for(int i = 1;i <= n;i++){if(s[i] == 'o'){ans += l * 2 + 1;l++;}else if(s[i] == 'x'){l = 0.0;}else if(s[i] == '?'){ans += (l * 2.0 + 1.0) * 0.5;l = (l + 1.0) * 0.5;}}printf("%.4f\n",ans);return 0;
}

这篇关于BZOJ3450. Tyvj1952 Easy（期望dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---