Description

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 /*做完這道題目算是對期望DP稍有理解dp[i]表示匹配到第i個字符的期望值，然后我們考慮是否匹配，如果匹配了，它對答案的貢獻是(x+1)^3-x^3=3*x^3+3*x^2+1，此處x是前面的期望得到的全1串的長度，然后維護x^2的期望值和x的期望值就行了。 */ #include<cstdio> #include<iostream> #define N 100010 using namespace std; double a[N],f1[N],f2[N],f3[N];int n; int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lf",&a[i]);f1[i]=(f1[i-1]+1)*a[i];f2[i]=(f2[i-1]+2*f1[i-1]+1)*a[i];f3[i]=f3[i-1]+(3*f2[i-1]+3*f1[i-1]+1)*a[i];}printf("%.1lf",f3[n]);return 0; }

?

轉載于:https://www.cnblogs.com/harden/p/6498634.html

總結

以上是生活随笔為你收集整理的OSU!（bzoj 4318）的全部內容，希望文章能夠幫你解決所遇到的問題。

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