【题目来源】
洛谷：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\) 位小数。
【输入样例】
3
0.5
0.5
0.5
【输出样例】
6.0
【解题思路】
【算法标签】
《洛谷 P1654 OSU!》 #动态规划DP#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n;
double x1[N], x2[N], f[N], p;int main()
{cin >> n; // 输入序列长度nfor (int i=1; i<=n; i++){cin >> p; // 输入第i个位置成功的概率p// 计算x1[i]: 以i结尾的连续成功长度的期望// 公式推导：// 如果i位置成功(概率p): 连续成功长度 = 以i-1结尾的连续成功长度 + 1// 如果i位置失败(概率1-p): 连续成功长度 = 0// 所以: x1[i] = p * (x1[i-1] + 1) + (1-p) * 0 = (x1[i-1]+1) * px1[i] = (x1[i-1]+1) * p;// 计算x2[i]: 以i结尾的连续成功长度平方的期望// 公式推导：// 设L是i-1位置结尾的连续成功长度// 如果i位置成功: 新的连续长度 = L+1, 平方 = (L+1)^2 = L^2 + 2L + 1// 如果i位置失败: 新的连续长度 = 0, 平方 = 0// 所以: x2[i] = p * (x2[i-1] + 2*x1[i-1] + 1) + (1-p) * 0x2[i] = (x2[i-1] + 2*x1[i-1] + 1) * p;// 计算f[i]: 到位置i为止的所有连续成功长度三次方的期望和// 公式推导：// 在位置i新增的连续三次方和的期望 = p * (x2[i-1] + 3*x1[i-1] + 1)的期望// 因为(L+1)^3 = L^3 + 3L^2 + 3L + 1// 新增的期望 = p * (期望[L^3] + 3*期望[L^2] + 3*期望[L] + 1)// = p * (0 + 3*x2[i-1] + 3*x1[i-1] + 1)// 加上之前的累计和f[i-1]f[i] = f[i-1] + (3*x2[i-1] + 3*x1[i-1] + 1) * p;}printf("%.1lf", f[n]); // 输出最终结果，保留1位小数return 0;
}
【运行结果】
3
0.5
0.5
0.5
6.0