CF1860D 题解

· · 题解

首先考虑一个子问题，给两个只含有 0 和 1 的字符串 s, t，求至少要使用多少次交换 t 的任意两个字符的操作，使得 s 与 t 相等，或报告无解。

显然无解情况就是两个串 0 或 1 的出现次数不同。接下来我们排除相等的位置，设还剩 k 个 s_i = \texttt{0}, t_i = \texttt{1} 的位置和 k 个 s_i = \texttt{1}, t_i = \texttt{0} 的位置，每次选择一对 (0, 1) 交换，答案就是 k。

回到原题，发现 n \le 100，那不就直接把题面中乱七八糟的条件塞进 dp 状态吗。设 f_{i, j, k} 为 t 中填完 [1, i]，填了 j 个 0，当前 \texttt{01} 子序列个数减去 \texttt{10} 子序列个数 = k，t 与 s 不相等的位置个数的最小值。转移就枚举第 i 个位置填 0 还是 1，如果填 1，那么 k 加上 [1, i - 1] 中 0 的个数，否则 k 减去 [1, i - 1] 中 1 的个数。

时间复杂度 O(n^4)。

code