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}\) 解决。
虚假的 \(\text{dp}\)，真实的贪心
CF1763D Valid Bitonic Permutations
看到数据范围都很小啊，考虑枚举拐点 \(\text{id}\) 在哪个位置。首先有个很容易被忽略的隐藏条件（也有可能是我比较逊没想到），拐点的数值必是 \(n\)。然后拐点在每个位置的贡献就可以暴力分为 \(6\) 类：
\[\begin{cases}
\binom{x-y-1}{j-i-1}\binom{y-1}{n-j}\binom{n-x-1}{i-id-1}\left [ x > y \right ] &\text{if}\ \ id < x\\
\binom{x-y-1}{j-i-1}\binom{y-1}{n-j}\left [ x > y \right ]\left [ x = n \right ] &\text{if}\ \ id = x\\
\binom{n-y-1}{j-id-1}\binom{x-1}{i-1}\binom{y-1-x}{n-j-(x-1-(i-1))}\left [ x < y \right ] &\text{if}\ \ x < id < y\\
\binom{n-x-1}{id-i-1}\binom{y-1}{n-j}\binom{x-1-y}{i-1-(y-1-(n-j))}\left [ x > y \right ] &\text{if}\ \ x < id < y\\
\binom{y-x-1}{j-i-1}\binom{x-1}{i-1}\left [ x < y \right ]\left [ y = n \right ] &\text{if}\ \ id = y\\
\binom{y-x-1}{j-i-1}\binom{x-1}{i-1}\binom{n-y-1}{id-j-1}\left [ x < y \right ] &\text{if}\ \ id > y
\end{cases}\]
除了中间两类（拐点不在中间的时候）都很好理解啊，考虑拐点在中间的情况，以 \(x < y\) 为例。先把一定不冲突的选掉，即 \(\text{id}\) 到 \(j\) 中间的与 \(i\) 之前的。剩下比 \(x\) 小的必然放在 \(j\) 右边，再把比 \(y\) 小的剩下数选一些填满 \(j\) 的右边，最后剩下的数排在 \(i\) 和 \(\text{id}\) 间。
真实的数学，虚假的 \(\text{dp}\)