bzoj3450 Tyvj1952 Easy（期望DP）题解

题意

给定一个序列，一些位置未确定（是(o)与(x)的几率各占(50\%)）。对于一个(ox)序列，连续(x)长度的(o)会得到(x^2)的收益，请问最终得到的序列的期望收益是多少？

算法

期望DP

思路

一段一段地处理其实并不方便，因为我们并不知道一段连续(o)的长度（它会随着你的选择而变化）。

于是换一个思路，发现题目计算答案的方式是平方，而((x+1)^2=x^2+2x+1)，也就是说，假如前一个位置连续的(o)的长度为(x)且当前位为(o)，那么对答案的额外贡献就是(2x+1)。（看起来就很DP）

设(l_i)为到第(i)个位置的连续(o)的期望长度，那么：

• 若(c_i=o)，则(l_i=l_{i-1}+1)，对答案的贡献为(2 imes l_{i-1}+1)。
• 若(c_i=x)，则(l_i=0)，对答案的贡献为(0)。
• 若(c_i=?)，则(l_i= frac {l_{i-1}+1}{2})（因为有一半的可能性选到(x)），对答案的贡献为(frac{l_{i-1} imes 2+1}{2})。

推一遍就好了。

参考代码

/*
 * @Author: When_C 
 * @Date: 2020-11-17 20:18:41 
 * @Last Modified by: When_C
 * @Last Modified time: 2020-11-17 20:38:54
 */
#include <cstdio>
#include <iostream>

using namespace std;

const int maxn = 3e5 + 10;
int n;
double l[maxn],f[maxn],Ans;
char c[maxn];

int main(){
    scanf("%d%s", &n, c + 1);
    for(int i = 1; i <= n; ++ i){
        if(c[i] == 'x') l[i] = 0;
        else if(c[i] == 'o') l[i] = l[i - 1] + 1.0, Ans += l[i - 1] * 2 + 1.0;
        else{
            l[i] = (l[i - 1] + 1.0) / 2;
            Ans += (l[i - 1] * 2 + 1.0) / 2;
        }
    } printf("%.4lf
", Ans);
    return 0;
}

更多

事实上，这道题还有一个升级版

其他的基本上没改（还更方便了），就是把计算方法改成了长度的立方。其实做法也差不多，但是注意除了维护(l_i)和(Ans)以外，还要维护一个(l'_i)，表示期望的长度平方，因为期望长度的平方与期望的长度平方是不一样的（有没有体会到出题人的绕口令呢）。

顺便贴下代码吧：

/*
 * @Author: When_C 
 * @Date: 2020-11-17 20:18:41 
 * @Last Modified by: When_C
 * @Last Modified time: 2020-11-17 21:24:24
 */
#include <cstdio>
#include <iostream>

using namespace std;

const int maxn = 1e5 + 10;
int n;
double l1,l2,Ans;

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i){
        double p; scanf("%lf", &p);
        Ans += (l2 * 3 + l1 * 3 + 1) * p;
        l2 = (l2 + l1 * 2 + 1) * p;
        l1 = (l1 + 1) * p;
    } printf("%.1lf
", Ans);
    return 0;
}