简单的期望DP
分三种情况考虑就可以了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=300005;
int n;
double F[N],D[N];
char s[N];
int main(){
freopen("3450.in","r",stdin);
freopen("3450.out","w",stdout);
scanf("%d %s",&n,s+1);
for(int i=1;i<=n;i++){
if(s[i]=='o'){F[i]=F[i-1]+D[i-1]*2+1;D[i]=D[i-1]+1;}
if(s[i]=='x'){F[i]=F[i-1];D[i]=0;}
if(s[i]=='?'){F[i]=F[i-1]+(D[i-1]*2+1)/2;D[i]=(D[i-1]+1)/2;}
}
printf("%.4lf\n",F[n]);
return 0;
}
评论 (0)
