D

有一排高度都为h的树,每次选择最左或最右边一棵砍倒,向左倒概率为p,向右倒为1-p
一棵树可以击倒若干棵树,倒向显然相同
问树木全被砍倒后,地面上树木长度的并的期望

区间dp 概率dp
我们直接模拟砍树的过程即可,连续击倒的区间可以预处理出来。
$d_{l,r,a,b}$ 表示区间[l,r]的树还没被砍倒,l-1是否向右倒,r+1是否向左倒
然后有四种转移,需要注意的是l向右倒和r向左倒的时候可能会将[l,r]全被击倒。

复杂度$O(n^2)$

E

一个矩阵,每个位置有一个数d(0-9),每次走到$(x+a_d,y+b_d)$,若不在矩阵内则还留在原处
给出q个字符串,判断每个串是否为其中一条路径子序列

DP

预处理 $d_{x,y,c}$ 表示在(x,y),最近的字符为c的点的位置
然后直接暴力判断

复杂度$O(nmq + \sum|s_i|)$

然而有人表示$O(n^2m^2q + \sum|s_i|)$ 的算法也能过,即每次从入度为0的节点开始dfs
因为能卡掉其的数据比较难构,实际运行时还是比较快的。