【期望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%

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=+;
int n;
char s[MAXN];
double f[MAXN],g[MAXN]; int main()
{
scanf("%d",&n);
scanf("%s",s+);
f[]=g[]=;
for (int i=;i<=n;i++)
{
if (s[i]=='x') f[i]=f[i-],g[i]=;
if (s[i]=='o') f[i]=f[i-]+*g[i-]+,g[i]=g[i-]+;
if (s[i]=='?') f[i]=f[i-]+g[i-]+0.5,g[i]=(g[i-]+)/;
}
printf("%.4lf",f[n]);
return ;
}
上一篇:处理不等高TableViewCell


下一篇:python基础——字符串和编码