php网站怎么做缓存/百度seo搜索引擎优化厂家

dp[i] 为以 i 结尾的答案，cnt[i] 为以 i 结尾的连续 o 的期望个数。

然后当遇到 ‘?’ 时，考虑两种转移合并即可。

然后，这个数组可以滚动优化。

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=3e5+10;
int n; double dp,cnt; char str[N];
signed main(){scanf("%d %s",&n,str+1);for(int i=1;i<=n;i++){if(str[i]=='o') dp=dp+2*cnt+1,cnt++;else if(str[i]=='x') cnt=0;else dp=(dp*2+2*cnt+1)/2.0,cnt=(cnt+1)/2.0;}printf("%.4lf\n",dp);return 0;
}