[bzoj3450]Tyvj1952 Easy[概率dp]

和之前一样考虑这个音符时x还是o，如果是x，是否是新的连续一段，对答案的贡献是多少$(a^2-{(a-1)}^2)$，然后递推就可以了。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 char    str[310000];
 6 long double    p[310000],l[310000];
 7 
 8 int main()
 9 {
10     int    n,i;
11 
12     scanf("%d",&n);
13     scanf("%s",str+1);
14     for(i=1;i<=n;++i)
15     {
16         if(str[i]=='o')p[i]=p[i-1]+2*l[i-1]+1,l[i]=l[i-1]+1;
17         else if(str[i]=='x')p[i]=p[i-1];
18         else    p[i]=p[i-1]+l[i-1]+0.5,l[i]=(l[i-1]+1)/2;
19     }
20     printf("%.4Lf
",p[n]);
21     return 0;
22 }