某谷 P1654 OSU!

題目背景

原 《產(chǎn)品排序》 參見P2577

題目描述

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

我們可以把osu的規(guī)則簡化與改編成以下的樣子:

一共有n次操作，每次操作只有成功與失敗之分，成功對(duì)應(yīng)1，失敗對(duì)應(yīng)0，n次操作對(duì)應(yīng)為1個(gè)長度為n的01串。在這個(gè)串中連續(xù)的?XX?個(gè)?11?可以貢獻(xiàn)?X^3X3?的分?jǐn)?shù)，這x個(gè)1不能被其他連續(xù)的1所包含（也就是極長的一串1，具體見樣例解釋）

現(xiàn)在給出n，以及每個(gè)操作的成功率，請(qǐng)你輸出期望分?jǐn)?shù)，輸出四舍五入后保留1位小數(shù)。

輸入輸出格式

輸入格式：

第一行有一個(gè)正整數(shù)n,表示操作個(gè)數(shù)。接下去n行每行有一個(gè)[0,1]之間的實(shí)數(shù)，表示每個(gè)操作的成功率。

輸出格式：

只有一個(gè)實(shí)數(shù)，表示答案。答案四舍五入后保留1位小數(shù)。

輸入輸出樣例

輸入樣例#1：?

3 0.5 0.5 0.5

輸出樣例#1：?

6.0

說明

【樣例說明】

000分?jǐn)?shù)為0，001分?jǐn)?shù)為1，010分?jǐn)?shù)為1，100分?jǐn)?shù)為1，101分?jǐn)?shù)為2，110分?jǐn)?shù)為8，011分?jǐn)?shù)為8，111分?jǐn)?shù)為27，總和為48，期望為48/8=6.0

N<=100000

?

?

Solution

典型的期望DP

DP分別維護(hù)? ??的期望即可。

#include<bits/stdc++.h> using namespace std; const int MAXN=1e5+50; double p[MAXN],s1[MAXN],s2[MAXN],ans[MAXN]; inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } int main() {int n=read();for(int i=1;i<=n;i++) scanf("%lf",&p[i]);for(int i=1;i<=n;i++){s1[i]=(s1[i-1]+1)*p[i];s2[i]=(s2[i-1]+2*s1[i-1]+1)*p[i];ans[i]=ans[i-1]+((s1[i-1]+s2[i-1])*3+1)*p[i];}printf("%.1lf",ans[n]);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的某谷 P1654 OSU!的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。