【P1654】OSU! 题解

pldzy · 2023-03-27 20:10:03 · 个人记录

期望 dp。

LG 传送门

自己的做法时间上过不去，且没有运用期望的优越性。

Solution

重新梳理一下思路。

首先一定要注意，求的是期望！而不是单纯的总权值。

那么对这道题，我们可以转化为：f_i 表示，经过这一位之后，期望总分数增加了多少期望分。

即，若假定所求答案为 ans_i，输出答案为 ans_n，那么 f_i=ans_{i}-ans_{i-1}。

那么，我们显然有 p_i 的概率，让 ans_{i-1} 加上某个值；

有 1-p_i 的概率，让 ans_{i-1} 什么也不加。

考虑第一种情况。

我们会加上多少值呢？通过大力拆分，我们拆分 (x+1)^3-x^3，得到一个二次三项式。

若当前填入 1，则会比上一个答案多了 3x^2+3x+1。

有那么多种情况，如何确定 x 的值是多少呢？

这时候求期望的优越性就体现出来了。若把期望感性理解为平均值，那么我只需要线性维护 x^2 和 x 的期望（平均）值即可。

线性维护 x^2 和 x 的过程，可以理解为此题的弱化版。

综上，f_i=0\times (1-p_i)+(3x^2+3x+1)\times p_i。

那么最后 ans_n=\sum_{i=1}^nf_i。

Code

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i <= b; ++i)
const int maxn = 1e5 + 5;
typedef double db;
int n;
db p[maxn], x1[maxn], x2[maxn], f[maxn];
db ans;

int main(){
    scanf("%d", &n);
    rep(i, 1, n) scanf("%lf", &p[i]);
    rep(i, 1, n){
        x1[i] = (x1[i - 1] + 1) * p[i];
        x2[i] = (x2[i - 1] + 2 * x1[i - 1] + 1) * p[i];
        f[i] = (3 * x2[i - 1] + 3 * x1[i - 1] + 1) * p[i];
    }
    rep(i, 1, n) ans += f[i];
    return printf("%.1lf", ans), 0;
} 

Thanks for reading.