洛谷P1654 OSU! 题解

题目链接：P1654 OSU!

题意：

osu 是一款群众喜闻乐见的休闲软件。

我们可以把osu的规则简化与改编成以下的样子:

一共有 \(n\) 次操作，每次操作只有成功与失败之分，成功对应 \(1\) ，失败对应 \(0\) ，\(n\) 次操作对应为 \(1\) 个长度为 \(n\) 的 01 串。在这个串中连续的 \(X\) 个 \(1\) 可以贡献 \(X^3\) 的分数，这 \(X\) 个 \(1\) 不能被其他连续的 \(1\) 所包含（也就是极长的一串 \(1\) ，具体见样例解释）

现在给出 \(n\) ，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留 \(1\) 位小数。

输入格式：

第一行有一个正整数 \(n\) ，表示操作个数。接下去 \(n\) 行每行有一个 \([0,1]\) 之间的实数，表示每个操作的成功率。

输出格式：

只有一个实数，表示答案。答案四舍五入后保留 \(1\) 位小数。

数据范围：

\(1 \le n \le 10^5\)

显然期望dp。但是这个贡献不太好计算。

因为它是一个整体去算的，而 dp 的过程中整体的信息会丢失。

因此我们考虑增加一个 \(1\) 对原来的串的贡献。 \[ \Delta = (x+1)^3 - x^3=3x^2 + 3x + 1 \] 二项式定理易得上式。因此我们可以记录 \(f_i,g_i,h_i\) 分别标记 \(x,x^2\) 每一维的期望以及答案，则 \[ f_i = (f_{i-1} + 1)\times p_i \\g_i = (g_{i-1} + 2f_{i-1} + 1)\times p_i \\h_i = h_{i-1} + (3g_{i-1}+3f_{i-1}+1)\times p_i \] 最后答案就是 \(h_n\) 。时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n;
double p[N],x1[N],x2[N],ans[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> p[i];
    for(int i=1; i<=n; i++)
    {
        x1[i] = (x1[i - 1] + 1) * p[i];
        x2[i] = (x2[i - 1] + 2 * x1[i - 1] + 1) * p[i];
        ans[i] = ans[i - 1] + (3 * (x1[i - 1] + x2[i - 1]) + 1) * p[i];
    }
    cout << fixed << setprecision(1) << ans[n] << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/1215365487zyc/solution-p1654