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);
}
```