DP优化

签到题看了半个小时；T2 没有考虑到只需要包含最优解即可，非要确定另一多余状态，只拿了部分分。

T3 只会考虑 “$x, y$ 的公共祖先中含有 $l$ 的概率”，不会高效计算“当二者的 $\operatorname{lca}$ 恰为 $l$ 时”的期望/概率与总长之和的乘积，仍然只有暴力分。

T4 无思路。

一句话（?）题解

A – 签到题

可以简单用归纳法证明，仅有所有管道中通行时间最大的会阻塞进度，是为两数据包到达终点的时间间隔。算出首个数据包到达的时间再将前者相加即可。

B – 简单题

第一反应是类似笛卡尔树一样，在区间上依次合并区域最大值并计算贡献。$n \leq 300$ 似乎也在暗示这是一个区间 DP。

$\text{48 pts}$ 做法

设 $f(l,r,\text{mx})$ 表示“考虑完成区间 $[l,r]$ 内所有贡献，且最大值恰好为 $\text{mx}$”的最大权值和。转移时从小到大枚举最大值 $\text{mx}=V_{i,j}$，枚举包含它的区间，尝试转移 $$f(l,r,\text{mx})\leftarrow f(l,i-1,\text{mx}’)-C_{i,j}+\text{mx}\cdot \operatorname{calc}(l,r,i)+f(i+1,r,\text{mx}”)$$，其中 $\operatorname{calc}(l,r,i)$ 计算 $\sum_{l’=l}^{i}\sum_{r’=i}^{r}Q_{l’,r’}$，可以由二维前缀和实现。稍加演算会发现，这样转移不会重复计算贡献。时间复杂度 $\operatorname{O}(\sum K_{i}N^2)$。 （更多…）