题解：P13272 [NOI 2025] 序列变换

· · 题解

考场做法。

我们先考虑解决问题一。

考虑进行一次操作后，a_i 就会变成 0 了；在这之后，对 a_i 进行的任何操作就都没有意义了，我们实际上把整个序列分成了互不干扰的两段，可以进行递归求解。

这样容易设计出一个区间 dp：计 f_{l, r, x, y} 表示目前考虑区间 [l, r]，a_l=x，a_r=y，其能操作得到的最大答案。容易发现状态数不会很多，因此可以套一个记忆化搜索求解，根据实现的常数，可获得 12 到 24 分不等。

因此，若左边的 a_j 要通过一系列操作影响到右边的 a_i，我们必须依次进行 (j, j+1), (j+1, j+2) 一直到 (i-1, i) 为止，则此时 [j, i-1] 内的所有数都变成了 0，而 a_i 恰好为 [j, i] 内所有数的错位和；对于从右往左推也是如此。

我们让 [l, r, k] 代表一组操作 (l, l+1),(l+1, l+2)...(k-1, k) 以及 (r, r-1), (r-1, r-2)...(k+1, k)，容易发现这样的每个区间之间互不干扰，而且最终只有 a_k 有值，其值恰好等于整个区间的错位和的绝对值。

于是可以设计出一个朴素的序列 dp。令 f_i 表示当前序列划分到 i，前 i 项的答案，转移时我们枚举 j,k，并 O(n) 检查是否合法，即可做到 O(n^4)，稍加优化即可做到 O(n^3)； 容易发现，对于一个 j，合法的 k 应为一段前缀；对于一个 i，合法的 k 应该为一对后缀，则对于区间 [j, i]，我们只需要预处理出左右端点合法的 k 的前后缀区间，进行取交即可得到最后合法的 k，这样就容易做到 O(n^2) 了。

对于问题二，容易发现其与问题一类似，但倘若操作 [l, r, k] 后 a_k=0，则会将 k 不同的情况算重，只需进行一些特殊判断即可。

具体实现时，需要注意判断一下 k 与 r 的奇偶性与[l, r] 的错位相加和的符号有关，处理一下细节就好了。