BZOJ3450:Tyvj1952 Easy 期望dp

思路:

一开始yy了一个傻逼的\(O(n^2)\)的dp.

首先用'x'分成若干段,其中每一段都只有'o'或是'?'.

然后令\(f_i\)表示第\(i\)个'?'结尾是'x'的期望得分.显然可以枚举前面的'?'作为结尾'x'的情况进行转移.

不过这样是\(O(n^2)\),而且我并没有找到什么靠谱的优化方法.

于是又无节操膜拜题解.

设\(f_i\)表示以第\(i\)的位置结尾时的期望得分,\(l_i\)表示结尾的期望长度.

期望得分转移时有一些麻烦:

若当前是'x',有\(f_i=f_{i-1}\);

若当前是'o',有\(f_i=f_{i-1}+2l_{i-1}+1\),这个可以通过分类讨论得到;

若当前是'?',事实上也就是'x','o'的几率各占一半,即它们平分贡献,即\(f_i=f_{i-1}+\frac{2l_{i-1}+1}{2}\)

期望长度就很好转移了.

这样就可以\(O(n)\)解决了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
#define N 300010
char s[N];
f2 f[N],l[N];
int main(){
    int n;scanf("%d",&n);scanf("%s",s+1);
    for(int i=1;i<=n;++i){
        if(s[i]=='x')f[i]=f[i-1],l[i]=0;
        else if(s[i]=='o')f[i]=f[i-1]+2*l[i-1]+1,l[i]=l[i-1]+1;
        else f[i]=f[i-1]+l[i-1]+0.5,l[i]=0.5*(l[i-1]+1);
    }printf("%.4lf",f[n]);
    return 0;
}