7.17~7.18 DP专场

标签：begin 7.17 end 7.18 DP bmatrix dp

CF1814E Chain Chips

好久没写这种题了~~

不带修时，为了让总距离和最短，考虑让相邻的车互换位置，但如果单纯这样有可能剩下一辆车，那就让相邻的三辆车换一下。发现当车的个数 \(x \ge 4\) 时，都可以拆成 \(2\) 辆或 \(3\) 辆车。对应到边就是只能选相邻的一条边或两条边。设 \(dp_i\) 表示第 \(i\) 条边必选且满足条件的答案，那么：

\[dp_i = \min(dp_{i-1}, dp_{i-2}) + a_i \]

利用加法对取 \(\text{min}\) 操作的分配律，转化为广义矩乘递推：

\[\begin{bmatrix} dp_{i-2} & dp_{i-1} \end{bmatrix} \begin{bmatrix} \infty & a_i \\ 0 & a_i \end{bmatrix} = \begin{bmatrix} dp_{i-1} & dp_i \end{bmatrix}\]

用线段树维护支持修改。

CF1774E Two Chess Pieces

考虑每个棋子必须经过哪些点：

• 子树里有己方标记点的点
• 与子树中对方最深标记点距离大于 \(d\) 的点

除根结点外每个需经节点贡献为 \(2\)，一遍 \(\text{dfs}\) 解决。

标签：begin,7.17,end,7.18,DP,bmatrix,dp
From： https://www.cnblogs.com/Semorius/p/17566462.html