3450: Tyvj1952 Easy

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?876??Solved:?648
[Submit][Status][Discuss]

Description

某一天WJMZBMR在打osu~~~但是他太弱逼了，有些地方完全靠運氣:(
我們來簡化一下這個游戲的規則
有n次點擊要做，成功了就是o，失敗了就是x，分數是按comb計算的，連續a個comb就有a*a分，comb就是極大的連續o。
比如ooxxxxooooxxx，分數就是2*2+4*4=4+16=20。
Sevenkplus閑的慌就看他打了一盤，有些地方跟運氣無關要么是o要么是x，有些地方o或者x各有50%的可能性，用?號來表示。
比如oo?xx就是一個可能的輸入。
那么WJMZBMR這場osu的期望得分是多少呢？
比如oo?xx的話，?是o的話就是oooxx => 9，是x的話就是ooxxx => 4
期望自然就是(4+9)/2 =6.5了

Input

第一行一個整數n，表示點擊的個數
接下來一個字符串，每個字符都是ox？中的一個

Output

一行一個浮點數表示答案
四舍五入到小數點后4位
如果害怕精度跪建議用long double或者extended

Sample Input

4
????

Sample Output

4.1250


n<=300000
osu很好玩的哦
WJMZBMR技術還行(霧),x基本上很少呢

HINT

?

Source

我們都愛GYZ杯

?

/* f[i]表示到第i位的得分期望 L[i]表示已i結尾的長度期望 可知如果是o:L[i]=L[i-1]+1 由(L+1)^2=L^2+2*L+1可得 f[i]=f[i-1]+2*L[i-1]+1 如果是x:f[i]=f[i-1],L[i]=0; 如果是?:L[i]=(L[i-1]+1)/2 f[i]=(2*f[i-1]+2*L[i-1]+1)/2; */ #include<iostream> #include<cstdio> #include<cstring> #include<cmath>#define N 300007using namespace std; int n,m,k,cnt; double ans,f[N],L[N]; char s[N],ch[N];int main() {scanf("%d",&n);scanf("%s",s+1);f[0]=0;n=strlen(s+1);for(int i=1;i<=n;i++) {if(s[i]=='o') L[i]=L[i-1]+1,f[i]=f[i-1]+2*L[i-1]+1;else if(s[i]=='x') f[i]=f[i-1];else if(s[i]=='?') L[i]=(L[i-1]+1.0)/2.0,f[i]=f[i-1]+L[i-1]+0.5;}printf("%.4lf\n",f[n]);return 0; }

?

轉載于:https://www.cnblogs.com/L-Memory/p/7798980.html

總結

以上是生活随笔為你收集整理的bzoj3450 Easy(概率期望dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。