一起玩音游

NC232849. 一起玩音游

描述

简化过的音游中，每次游戏有 $n$ 次点击，每次点击有好和不好两种可能的结果，其中好表示为"O"，不好表示为"X"，则每次游戏可以表示为一个长度为 $n$ 的字符串。游戏的得分可以用该字符串进行计算：对于每个最长的连续"O"串，其对分数的贡献为自身长度的平方。例如"OXXOOXOOO"，其中有三个最长的连续"O"串："O"、"OO"、"OOO"，则分数为 $1^2+2^2+3^2=14$ 。若字符串中没有"O"，则分数为0。

现在给出每次点击是好的概率，其中第 $i$ 次为好的概率为 $p_i$ 。求游戏分数的期望值。

输入描述

第一行输入一个整数 ()，表示点击数。
第二行输入个实数 ()，每个实数至多有6位小数。

输出描述

输出一行一个实数，表示分数的期望值，与答案的绝对或相对误差不超过即为正确。

示例1

输入:

3
0.5 0.5 0.5

输出:

2.750000000000000

说明:

对于第一个样例，有8种可能：

"OOO"=9

"OOX"=4

"OXO"=2

"OXX"=1

"XOO"=4

"XOX"=1

"XXO"=1

"XXX"=0

故期望值为(9+4+2+1+4+1+1+0)/8 = 2.75

示例2

输入:

4
0.7 0.2 0.1 0.9

输出:

2.489200000000000

示例3

输入:

5
1 1 1 1 1

输出:

25.000000000000000

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 56ms, 内存消耗: 4908K, 提交时间: 2023-04-20 21:21:32

#include <vector>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;

#define endl '\n'
using LL=long long;
using LD=long double;
constexpr int N=1e5+10;
LD dp[N],len[N],p[N];

void solve() {
    int n;
    cin>>n;
    
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) {
        dp[i]=dp[i-1]+p[i]*(len[i-1]*2+1);
        len[i]=p[i]*(len[i-1]+1);
    }
    cout<<fixed<<setprecision(15)<<dp[n];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    solve();
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 67ms, 内存消耗: 432K, 提交时间: 2022-09-29 10:59:21

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&-x)
#define eps  1e-6
int n;
int main(){
    cin>>n;
    double explen=0;
    double expsc=0;
    double p;
    while(n--){
        cin>>p;
        expsc=expsc+(2*explen+1)*p;
        explen=(explen+1)*p;
    }

    cout<<setprecision(8)<<expsc;
}