【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;
}