P12392 题解

· · 题解

一个比官方题解更简单的做法。

数据范围与 T1 不同，这里 n\le 5000，所以 O(n^2) 的时间复杂度是可以接受的。这启发我们设计一个二维的 dp 解决问题。

否则，我们考虑任意一个最优策略，它在每个长度为 $l$ 的全部相等的连续段当中一定修改了 $[\frac{l}{2}]$ 个位置。 令 $0$ 表示没有进行修改，$1$ 表示进行了修改操作，则 $l$ 为奇数时，唯一的可能是形如 $0101010\cdots0$。 而 $l$ 为偶数时，一定存在一个偶数位置作为分界点，前面形如 $0101010\cdots1$，后面形如 $101010\cdots0$。 将它们分割成若干个 $01$ 和 $10$，如果 $l$ 为奇数就把最后一个 $0$ 单独拿出来。 现在对这个分割状态进行 `dp`，令 $f_{i,j,0/1/2}$ 为前 $i$ 个数进行了 $j$ 次修改，最后一个连续段形如 $0/01/10$ 的方案数。 这里定义一种“方案”为：在这 $i$ 个位置内填入 $[1,m]$ 的数作为原来的 $a$，再在放了 $1$ 的位置上进行修改使得相邻位互不相同。 初始令 $f_{1,0,0}=m,f_{2,0,0}=f_{2,0,1}=f_{2,0,2}=m(m-1)$。 转移方程为： $$f_{i,j,0}=(f_{i-1,j,0}+f_{i-1,j,1}+f_{i-1,j,2})(m-1)$$ $$f_{i,j,1}=(f_{i-2,j-1,0}+f_{i-2,j-1,1}+f_{i-2,j-1,2})(m-1)^2$$ 每一位不能和前面一位相同，没有额外限制。 $$f_{i,j,2}=(m-1)(m-2)f_{i-2,j-1,0}+(f_{i-2,j-1,1}+f_{i-2,j-1,2})(m-1)^2$$ 注意这里从 $f_{i-2,j-1,0}$ 转移时第 $i$ 位不能和第 $i-2$ 位相同，因为这样会造出一个长度为奇数的连续段，它在 $f_{i,j,0}$ 中被统计。 之后就可以做到 $O(n^2)$ 了。~~可以用倍增 + FFT 做到 $O(n\log n)$ 但是我没写。~~