「Summary」2022-07-07 做题记录

我真的不会做。

2022-07-07

$\mathbb{CF1675G}$

link
原来这里还有个结论。
若有两个序列 $a,b$ ,如果一次只挪动一个元素，记 $sum_a$ 为 $a$ 的前缀和序列，$sum_b$ 为 $b$ 的前缀和序列，那么把 $a$ 挪成 $b$ 需要的最小的操作步数是 $\sum_{i=1}^{n - 1} \mid sum_{a_i} = sum_{b_i} \mid$ 。
有了结论后 dp 就比较舒服，设 $dp_{i, j, k}$ 表示前 $i$ 个数已经归位（单调不降）,当前位上的数是 $j$ ，且前缀和为 $k$ 。
转移方程则为 $dp_{i, j, k} = \min\{ dp_{i - 1, l, k - j} + \mid j - sum_i \mid \}$ 。

$\mathbb{CF1144G}$

link
用贪心冲过去了。
你可以直观的感受一下这道题，想象有两根线，一根斜率是正的，另一根斜率是负的，把这两根线分段，交错着拼到一起。
like this.本来有个图的，但是画的太抽象了。。。
于是，你考虑能不能让当前这个点尽可能接到前一个点后面，大力分类讨论就 ok 了。