11.2 联测

A

统计每种颜色四个方向的极值。

B

非常好概率期望，使我大脑宕机。

一个 $O(n^3)$ dp，暴力枚举每个位置 $x$，设 $f_{i,j,0/1}$ 表示当前时刻 $i$，位置在 $j$，有没有经过 $x$。

观察到每个时刻的 $a_i$ 是确定的，但是好像也没什么用。

正难则反，求对于所有前缀和的最大值 $<x$ 的序列 $\{a'\}$，$ans_x=\sum_a p^{cnt}(1-p)^{n-cnt}$。

其中 $cnt=\sum_i [a'_i=0]$。设 $g_{i,j,k}$ 表示当前时刻 $i$，前缀最大值为 $j$，当前前缀为 $k$ 的答案。

$(1-p) \times g_{i,j,k} \rarr g_{i+1,\max(j,k+a_i),k+a_i}\\ p \times g_{i,j,k} \rarr g_{i+1,j,k}$

考虑从后往前做这个 dp，这样就能省掉第三维了。

$(1-p) \times g_{i,j} \rarr g_{i-1,\max(0,j+a_i)}\\ p \times g_{i,j} \rarr g_{i-1,j}$