题链:
http://www.lydsy.com/JudgeOnline/problem.php?id=4318
题解:
期望 dp
如果我们能够得到以每个位置结尾形成的连续 1 的长度的相关期望, 那么问题就好解决了
定义 g[i]表示以 1 位置结尾的连续 1 的长度的期望
转移显然: g[i]=p[i]*(g[i]+1)
然后定义 h[i]表示以 1 位置结尾的连续 1 的长度的平方的期望
由于(x+1)^2=x^2+2x+1,
所以 h[i]=p[i]*(h[i-1]+2*g[i-1]+1)
最后定义 f[i]表示 1~i 这个区间期望能得到的分数,
分为此时 i 位置得到 1 和得到 0 两种情况:
得到 1, 由于(x+1)^3=x^3+3*x^2+3x+1 那么贡献为: p[i]*(f[i-1]+3*h[i-1]+3*g[i-1]+1)
得到 0, 那么直接为前面的期望得分, 贡献为(1-p[i])*f[i-1]
所以 f[i]的转移为: f[i]=(得到 1)p[i]*(f[i-1]+3*h[i-1]+3*g[i-1]+1)+(得到 0)(1-p)*f[i-1];
.....................................................................
==, 难道没有感觉这个 f[i]的转移有一丝丝诡异么?
先看看这个错的做法,
多了一个 d[i], 表示以 i 结尾形成的连续 1 的长度的 3 次方的期望
那么其转移类似 g 和 h 的转移:
d[i]=p[i]*(d[i-1]+3*h[i-1]+3*g[i-1]+1)
然后再去求得 f[i], 同样地分为当前第 i 位得到 1 和得到 0 两种情况:
f[i]=(得到 1)d[i]+(得到 0)(1-p[i])*f[i-1]
乍一看似乎没问题, 但是在 (得到 1) 那里却出了问题:
f[i]表示的是 1~i 这个区间期望能够得到的分数,
但是在 (得到 1) 这个转移这里, 我们却只考虑了以 i 结尾的期望的那段 1 的贡献, 然而其它部分的贡献就没有转移过来
这也就是这个做法得到的答案比正确答案小的原因
- (可以强行把之前的贡献再加进来么? 233, 我反正加不来)
- .......................................................................
现在再反过来看看之前正确的 f[i]的求法 (没有 d[i] 数组的那个做法)
f[i]=(得到 1)p[i]*(f[i-1]+3*h[i-1]+3*g[i-1]+1)+(得到 0)(1-p)*f[i-1];
显然 (得到 0) 的那个转移没有问题
那么我们来想想 (得到 1) 的那么那个转移是如何解决掉那个错误做法出现的问题的
由于 f[i-1]表示的是区间 1~i-1 的期望得分,
那么我们就可以把 f[i-1]看成是由两个部分组成的:
一个部分是以 i-1 结尾的期望的那段连续的 1 造成的贡献 A(一个长度的 3 次方的期望), 另一部分则是其它部分的贡献 B:
所以 (得到 1) 这个转移可以看成是: p[i]*(B+A+3*h[i-1]+3*g[i-1]+1),
显然, 后面的 A+3*h[i-1]+3*g[i-1]+1 计算的就是以 i 结尾形成的连续 1 的长度的 3 次方的期望,
而 B 则是其它部分的贡献
所以就是这样巧妙地把新的贡献和其它部分的贡献都统计进了 f[i]里面
以上就是个人的见解
代码:
- #include < bits / stdc++.h > #define MAXN 100005 using namespace std;
- double g[MAXN],
- h[MAXN],
- f[MAXN],
- p;
- int N;
- int main() {
- ios: :sync_with_stdio(0);
- cin >> N;
- for (int i = 1; i <= N; i++) {
- cin >> p;
- g[i] = p * (g[i - 1] + 1);
- h[i] = p * (h[i - 1] + 2 * g[i - 1] + 1);
- f[i] = p * (f[i - 1] + 3 * h[i - 1] + 3 * g[i - 1] + 1) + (1 - p) * f[i - 1];
- }
- cout << fixed << setprecision(1) << f[N] << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2523293.html