【ybt金牌导航1-1-3】【luogu P1365】期望收益 / WJMZBMR打osu!/Easy

期望收益 / WJMZBMR打osu!/Easy

题目链接：ybt金牌导航1-1-3 / luogu P1365

题目大意

给定一个序列，一些位置未确定（是 o 与 x 的概率各占 50% ）。对于一个 ox 序列，连续 a 长度的 o 会得到 a^2 的收益，求最终得到的序列的期望收益。

思路

我们发现如果直接按期望收益 dp 会 n方超时。

那我们考虑 dp 别的期望，然后 dp 的时候统计出 ans。

那 dp 什么呢？

因为收益与每一段 o 串的长度有关，那我们就 dp 有关最后一个 o 串的期望长度。

对于 d p i dp_i dpi​：

1. 如果这一位已经确定是 o，那就直接是原来的长度加一（百分之一百）。
2. 如果只以为已经确定是 x，那就直接是 0 0 0（百分之一百）。
3. 那如果不确定，那就是百分之五十是 x，百分之五十是 o，也就是说是原来的长度加一再除以二。

那么怎么统计出 ans。

因为是长度的平方，然后长度可能每次加一，那我们自然会想到这个式子： ( x + 1 ) 2 = x 2 + 2 x + 1 (x+1)^2=x^2+2x+1 (x+1)2=x2+2x+1。

那我们就可以在前面 dp 的三种情况中，ans 要加的值：

1. 因为是原来的长度加一，所以是加 2 × d p i − 1 + 1 2\times dp_{i-1}+1 2×dpi−1​+1
2. 现在的长度已经是 0，那答案也不用加了。（或者说加 0 0 0）
3. 那就是两个可能各一半的可能，那其实就是加 ( 2 × d p i − 1 + 1 ) × 0.5 (2\times dp_{i-1}+1)\times 0.5 (2×dpi−1​+1)×0.5

最后输出 a n s ans ans 即可。

代码

#include<cstdio>

using namespace std;

int n, a[300001];
double size[300001], ans;
char c;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		c = getchar();
		while (c != '?' && c != 'o' && c != 'x') c = getchar();
		
		if (c == '?') a[i] = -1;
			else if (c == 'o') a[i] = 1; 
	}
	
	for (int i = 1; i <= n; i++)
		if (a[i] == 1) {//已经固定了是o
			size[i] = size[i - 1] + 1.0;
			ans += 2.0 * size[i - 1] + 1.0;
		}
		else if (a[i] == 0) {//已经固定了是x
			size[i] = 0.0;
			ans += 0.0;
		}
		else {//不确定
			size[i] = (size[i - 1] + 1) * 0.5;
			ans += (2.0 * size[i - 1] + 1.0) / 2;
		}
	
	printf("%.4lf", ans);
	
	return 0;
}