一、题目
二、思路
等了整整一年，我洛谷的用户名终于改过来了！发篇题解庆祝一下。
这道题我们需要用到期望的线性递推，具体来说是这样子的。
首先，(x1[i])表示以(i)结尾（一定要注意）的连续1的期望长度。
同理，(x2[i])表示以(i)结尾的连续1的期望长度的平方。
所以，有(x1[i]=(x1[i-1]+1) imes p[i] + 0 imes (1-p[i]))，即(x1[i]=(x1[i-1]+1) imes p[i]).
同理，有(x2[i] = (x2[i - 1] + 2 * x1[i - 1] + 1) imes p[i]).
接下来考虑如何计算答案。
设(ans[i])表示(1sim i)的期望得分。（注意：和之前的定义不同，不一定以(i)结尾！）
那么，(ans[i] = ans[i - 1] + i ext{这个点对答案的贡献})。
我们又会发现，i对答案的贡献只和i之前的1有关，和i之后的无关。
如果i这一位是0，对答案没有贡献。
如果i这一位是1，则对答案有(3 imes x2[i - 1] + 3 imes x1[i - 1] + 1)的贡献。
所以(ans[i] = ans[i - 1] + (3 imes x2[i - 1] + 3 imes x1[i - 1] + 1) imes p[i])。
最终答案就是(ans[n])。
三、 代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
#define mem(s, v) memset(s, v, sizeof s)
inline LL read(void) {
LL x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return f * x;
}
const int maxn = 100005;
int n;
double p[maxn];
double x1[maxn], x2[maxn], ans[maxn];
int main() {
cin >> n;
for (register int i = 1; i <= n; ++i) {
cin >> p[i];
}
for (register 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 * x2[i - 1] + 3 * x1[i - 1] + 1) * p[i];
/*请大家思考上面这句话与
ans[i] = (ans[i - 1] + 3 * x2[i - 1] + 3 * x1[i - 1] + 1) * p[i];
的区别
*/
}
printf("%.1lf
", ans[n]);
return 0;
}