WJMZBMR 打 osu! / Easy 期望 dp 经典进阶题
Sweetlemon
2019-11-12 22:59:51
#### WJMZBMR 打 osu! / Easy
这题比 osu! 一些图的 Easy 难多了……
##### 随机变量
我们需要详细定义**随机变量**，这样有利于理解。注意，下面的几段都还没有引入期望。
随机变量的推导可以认为是涵盖了各种可能情况时的推导。再次提醒，这里还没有期望！
$L_i$ 表示以第 $i$ 个点击结尾的 combo 的**长度**。如果 $a_i$ 是 x，$L_i=0$；对于 o，$L_i=L_{i-1}+1$，也就是不论 $L_{i-1}$ 如何，只要 $a_i$ 是 o，$L_i$ 总是等于 $L_{i-1}+1$。对于 ?，情况比较复杂，$L_i$ 有 $\frac{1}{2}$ 的概率等于 $L_{i-1}+1$，有 $\frac{1}{2}$ 的概率等于 $0$。
$F_i$ 表示假如在第 $i$ 次点击后游戏意外退出（这个说法好牵强），此时的**得分**（或者可以理解为进行到第 $i$ 次点击时游戏界面显示的分数，打过 osu! 也大概知道吧(大雾)）。
考虑如何从 $F_{i-1}$ 计算 $F_i$ 呢？这当然是考虑第 $i$ 次点击对分数有多少贡献（或者叫增量）啦。假如第 $i$ 次点击 miss 了，那么 $F_i$ 当然等于 $F_{i-1}$（这个音符就白打了）。但是如果成功了，那么 combo 加长了 $1$，分数又增加了多少呢？
由于 $(x+1)^2=x^2+2x+1$，也就是 $(x+1)^2-x^2=2x+1$，将 $x=L_{i-1}$ 代入上面的式子，于是 combo 增长 $1$ 对答案的增加量应该是 $2L_{i-1}+1$。
因此，对于 x，$F_i=F_{i-1}$；对于 o，$F_i=F_{i-1}+2L_{i-1}+1$；对于 ?，上述两个等式成立的概率各为 $\frac{1}{2}$。
或者，我们可以定义随机变量 $\Delta_i=F_i-F_{i-1}$。对于 x，$\Delta_i=0$；对于 o，$\Delta_i=2L_{i-1}+1$；对于 ?，上述两个等式成立的概率各为 $\frac{1}{2}$。
---
##### 随机变量的期望
这些可都是随机变量的分布啊，我要它干什么呢？
算期望确实要用到概率，接下来我们开始了！
由于期望的线性性，$\mathrm{Ex}(F_i)=\mathrm{Ex}(F_{i-1}+\Delta_i)=\mathrm{Ex}(F_{i-1})+\mathrm{Ex}(\Delta_i)$。因此，我们只需要想办法计算出 $\mathrm{Ex}(\Delta_i)$，就可以很容易地递推出 $\mathrm{Ex}(F_i)$ 了（其实 $\mathrm{Ex}(F_i)$ 就是 $\mathrm{Ex}(\Delta_i)$ 的前缀和嘛）。
对于 x，由于 $\Delta_i$ 恒等于 $0$，因此 $\mathrm{Ex}(\Delta_i)=0$。
对于 o，由于 $\Delta_i$ 恒等于 $2L_i-1$，由期望的线性性，$\mathrm{Ex}(\Delta_i)=\mathrm{Ex}(2L_{i-1}+1)=2\mathrm{Ex}(L_{i-1})+1$。
对于 ?，我们要根据分布列计算 $\mathrm{Ex}(\Delta_i)$，也就是把两种情况下的取值与概率相乘，加权相加——这应该算是全期望公式的应用吧。由于 $\Delta_i$ 取上述两种式子的概率各为 $\frac{1}{2}$，因此 $\mathrm{Ex}(\Delta_i)=\frac{1}{2}(0+2\mathrm{Ex}(L_{i-1})+1)=\mathrm{Ex}(L_{i-1})+\frac{1}{2}$。
上面的三个式子中有两个出现了 $\mathrm{Ex}(L_{i-1})$，因此我们在计算 $\mathrm{Ex}(\Delta_i)$ 的同时也要计算 $\mathrm{Ex}(L_i)$。
对于 x，由于 $L_i$ 恒等于 $0$，因此 $\mathrm{Ex}(L_i)=0$。
对于 o，由于 $L_i$ 恒等于 $L_{i-1}+1$，由期望的线性性，$\mathrm{Ex}(L_i)=\mathrm{Ex}(L_{i-1}+1)=\mathrm{Ex}(L_{i-1})+1$。
对于 ?，我们还是要根据分布列计算 $\mathrm{Ex}(L_i)$。由于 $L_i$ 取上述两种式子的概率各为 $\frac{1}{2}$，因此 $\mathrm{Ex}(L_i)=\frac{1}{2}(0+\mathrm{Ex}(L_{i-1})+1)=\frac{1}{2}\mathrm{Ex}(L_{i-1})+\frac{1}{2}$。
这样我们所需的所有递推式都全了，可以整理如下：
$$\begin{cases}\begin{aligned} &\mathrm{Ex}(L_i)=0,&a_i=\mathrm{x} \\ &\mathrm{Ex}(L_i)=\mathrm{Ex}(L_{i-1})+1,&a_i=\mathrm{o} \\ &\mathrm{Ex}(L_i)=\frac{1}{2}\mathrm{Ex}(L_{i-1})+\frac{1}{2}, &a_i=\mathrm{?} \end{aligned}\end{cases}$$
$$\begin{cases}\begin{aligned} &\mathrm{Ex}(F_i)=\mathrm{Ex}(F_{i-1}),&a_i=\mathrm{x} \\ &\mathrm{Ex}(F_i)=\mathrm{Ex}(F_{i-1})+2\mathrm{Ex}(L_{i-1})+1,&a_i=\mathrm{o}\\ &\mathrm{Ex}(F_i)=\mathrm{Ex}(F_{i-1})+\mathrm{Ex}(L_{i-1})+\frac{1}{2}, &a_i=\mathrm{?} \end{aligned}\end{cases}$$
初始值是 $F_0=L_0=0$。因为我们已经把辅助变量 $\Delta_i$ 处理掉了，所以最终我们不需要用到它。
注意一个要点！$F_i$ 的式子里不要出现 $L_i$，因为这样在应用全期望公式的时候会出问题。简单地说，就是全期望公式里面已经在讨论这个 ? 是否 miss 的这两种可能性了，但是 $\mathrm{Ex}(L_i)$ 里面同样包含了这个 ? 是否 miss 的讨论，一个事件重复讨论就会导致问题；或者说，在全期望公式里，已经假设（或者说在……的条件下）了这个 ? 是否 miss，因此应该代入的是已经确定下来的上一个状态，而不是代入目前这个状态。
如果不好理解，可以试着把 $\mathrm{Ex}(F_i)=\mathrm{Ex}(F_{i-1})+\mathrm{Ex}(L_i)-\frac{1}{2},\ a_i=\mathrm{?}$ 代入 `?` 这个序列计算，就会发现问题。
----
##### 代码
下面是甚至不需要用到数组的代码。
另外，写完这题还可以写一道类似的 [osu!](https://www.luogu.org/problem/P1654)。
```cpp
#include <cstdio>
#include <cctype>
#include <algorithm>
#define MAXIOLG 25
#define FILENAME(x)\
freopen(x".in","r",stdin);\
freopen(x".out","w",stdout);
using namespace std;
typedef long long ll;
typedef long double ld;
typedef ll io_t;
io_t shin[MAXIOLG];
io_t seto(void); //快读
char seto_op(void); //读入 o,x,?
void ayano(io_t x,char spliter='\n'); //快速输出
int main(void){
int n;
n=seto();
ld exl=0,exf=0; //动态维护 Ex(L_i), Ex(F_i)
for (int i=1;i<=n;i++){
char ch=seto_op(); //读入当前音符
switch (ch){
case 'x':
exl=0; //Ex(F_i)=Ex(F_{i-1}), Ex(L_i)=0
break;
case 'o':
exf+=2*exl+1,exl++; //Ex(F_i)=Ex(F_{i-1})+2Ex(L_{i-1})+1, Ex(L_i)=Ex(L_{i-1})+1
//注意上面先更新 F，是因为 F 的更新需要用到原来的 L 值（道理类似于 01 背包倒序循环）
break;
case '?':
exf+=exl+0.5,exl++,exl/=2; //Ex(F_i)=Ex(F_{i-1})+Ex(L_{i-1})+0.5, Ex(L_i)=0.5*(Ex(L_{i-1}+1)
break;
}
}
printf("%.4Lf\n",exf);
return 0;
}
io_t seto(void){
io_t ans=0;
int symbol=0;
char ch=getchar();
while (!isdigit(ch))
(ch=='-')?(symbol=1):(0),ch=getchar();
while (isdigit(ch))
(ans=ans*10+(ch-'0')),ch=getchar();
return (symbol)?(-ans):(ans);
}
char seto_op(void){
char ch=getchar();
while (ch!='?' && ch!='o' && ch!='x')
ch=getchar();
return ch;
}
void ayano(io_t x,char spliter){
if (!x){
putchar('0'),putchar(spliter);
return;
}
if (x<0)
putchar('-'),x=-x;
int len=0;
while (x){
io_t d=x/10;
shin[len++]=x-d*10;
x=d;
}
while (len){
len--;
putchar(shin[len]+'0');
}
putchar(spliter);
}
```