題干：

osu 是一款群眾喜聞樂見的休閑軟件。?

我們可以把osu的規則簡化與改編成以下的樣子:?

一共有n次操作，每次操作只有成功與失敗之分，成功對應1，失敗對應0，n次操作對應為1個長度為n的01串。在這個串中連續的 X個1可以貢獻X^3 的分數，這x個1不能被其他連續的1所包含（也就是極長的一串1，具體見樣例解釋）?

現在給出n，以及每個操作的成功率，請你輸出期望分數，輸出四舍五入后保留1位小數。?

?

Input

第一行有一個正整數n,表示操作個數。接下去n行每行有一個[0,1]之間的實數，表示每個操作的成功率。?

?

Output

只有一個實數，表示答案。答案四舍五入后保留1位小數。?

?

Sample Input

3 0.5 0.5 0.5

Sample Output

6.0

Hint

?

【樣例說明】?

?

000分數為0，001分數為1，010分數為1，100分數為1，101分數為2，110分數為8，011分數為8，111分數為27，總和為48，期望為48/8=6.0?

?

N<=100000

題目大意：

給定一個序列，每個位置為 o?的幾率為?p_i??，為 x?的幾率為?1 - p_i??。對于一個 ox?序列，連續?x?長度的 o?會得到?x^3???的收益，問最終得到的ox?序列的期望收益是多少？

解題報告：

? 在上一個題（【BZOJ - 3450】）的基礎上，期望是x^3，做法如下：

第一步依舊是展開：

我們只需要維護?l1[i]為以?i為結尾的連續期望長度，l?2??[i]?為以?i?為結尾的連續長度的平方? 的期望。

，所以l2不能直接用l1得出。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int n; double p; double dp[MAX],l1[MAX],l2[MAX]; int main() {cin>>n;for(int i = 1; i<=n; i++) {scanf("%lf",&p);dp[i] = (3*l2[i-1]+3*l1[i-1]+1)*p;l1[i] = (l1[i-1]+1)*p;l2[i] = (l2[i-1]+(l1[i-1]*2+1))*p; }double ans = 0;for(int i = 1; i<=n; i++) ans += dp[i];printf("%.1f\n",ans);return 0 ; }

?

總結

以上是生活随笔為你收集整理的【BZOJ - 4318】OSU!（概率dp，数学期望，期望的线性性）的全部內容，希望文章能夠幫你解決所遇到的問題。

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