【期望DP】BZOJ3450- Tyvj1952 Easy

---恢复内容开始---

【题目大意】

有n次点击要做，成功了就是o，失败了就是x，分数是按comb计算的，连续a个comb就有a*a分，comb就是极大的连续o。求期望分数。

【思路】

比之前的OSU！简单好多的OSU。

设f[i]为期望分数,g[i]为期望末尾combo的长度。

①s[i]='x'，f[i]=f[i-1],g[i]=0；

②s[i]='o'，f[i]=f[i-1]+(g[i-1]+1)^2-g[i-1]^2=f[i-1]+2*g[i-1]+1,g[i]=g[i-1]+1

③s[i]='?'，①*50%+②*50%

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=300000+50;
 7 int n;
 8 char s[MAXN];
 9 double f[MAXN],g[MAXN];
10 
11 int main()
12 {
13     scanf("%d",&n);
14     scanf("%s",s+1);
15     f[0]=g[0]=0;
16     for (int i=1;i<=n;i++)
17     {
18         if (s[i]=='x') f[i]=f[i-1],g[i]=0;
19         if (s[i]=='o') f[i]=f[i-1]+2*g[i-1]+1,g[i]=g[i-1]+1;
20         if (s[i]=='?') f[i]=f[i-1]+g[i-1]+0.5,g[i]=(g[i-1]+1)/2;
21     }
22     printf("%.4lf",f[n]);
23     return 0;
24 }