BZOJ 3450 Tyvj1952 Easy ——期望DP

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

维护$x$和$x^2$的期望递推即可

#include <map>

#include <ctime>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

double l,ans;

char s[400005];

int n;

int main()

{

	scanf("%d",&n);

	scanf("%s",s+1);

	F(i,1,n)

	{

		if (s[i]=='o') ans+=2*l+1,l+=1;

		else if (s[i]=='x') l=0;

		else ans+=l+0.5,l=l/2+0.5;

	}

	printf("%.4f\n",ans);

}