Solution to CF1733D2 Zero-One (Hard Version)。
没做过简单版本，模拟赛上遇到，乍一看是个贪心，但贪心思维太弱想不到怎么贪。所以思考其他方法。
下文称同时取反 \(a_i\) 和 \(a_j\) 的一次操作为「取反 \((a_i, a_j)\)」，称 \(a_i=b_i\) 的状态为「匹配」。
思维关键点
若我们想要将 \((a_i,a_j)\) 取反，我们可以怎么做？
不难发现，分 \(a_i\) 与 \(a_j\) 相邻和不相邻两种情况：
\(a_i\) 与 \(a_j\) 相邻：
- 直接取反，代价为 \(x\)。
- 寻找到一个与 \(a_i\) 和 \(a_j\) 都不相邻的 \(a_k\)，先将 \((a_i,a_k)\) 取反，再将 \((a_j,a_k)\) 取反，代价为 \(2\times y\)。
\(a_i\) 与 \(a_j\) 不相邻：
- 直接取反，代价为 \(y\)。
- 将 \((a_i,a_{i + 1}),(a_{i + 1}, a_{i + 2}),\cdots,(a_{j - 1}, a_{j})\) 取反，代价为 \((j - i)\times x\)。
接下来考虑另一个问题：我们要取反哪些 \((a_i,a_j)\) 呢？
假设现在有 \(a_p\) 与 \(b_p\) 不匹配，\(a_q\) 与 \(b_q\) 不匹配，那么我们肯定选择将 \((a_p,a_q)\) 取反。
原因很简单，假设有 \(a_k=b_k\)，如果我们将 \((a_p,a_k)\) 取反，那么 \(a_k\ne b_k\)，我们需要额外的一次与 \(a_k\) 有关的操作将其复原。如果我们挑选一个 \(a_l=b_l\)，并将 \((a_k,a_l)\) 取反，那么 \(a_l\) 与 \(b_l\) 又会不匹配，又需要一次操作；如果挑选一个 \(a_l\ne b_l\)，并将 \((a_k,a_l)\) 取反，那么为什么不能在一开始就将 \((a_p,a_l)\) 取反呢？此时的 \(a_k\) 相当于一个中继，而这种情况我们已经在取反 \((a_p,a_l)\) 时考虑到了。
也就是说，我们每次取反 只 选择两个无法与 \(b\) 匹配的 \(a\)。
那么，有没有一种情况，让我们无法选择两个无法匹配的值呢？
那就是不匹配的值的数量有奇数个，才会让我们两个两个选的时候有元素落单。
不妨思考一次取反操作所有可能的情况（假设不受上面的结论限制）：
取反一个匹配值和一个不匹配值
此时匹配值变为非匹配，不匹配值变为匹配，不匹配的元素总数不变。
取反两个不匹配值
两个不匹配值都变为匹配，不匹配元素的总数量增加 \(-2\)。
取反两个匹配值
两个匹配值都变为非匹配，不匹配元素的总数量增加 \(2\)。
综上，一次操作对不匹配元素总数带来的更改只可能为 \(0,2,-2\)，均为偶数。当不匹配元素为奇数时，必定无法将其更改至刚好为 \(0\)。此时输出 \(-1\)。
我们上面结论的可实现性也得到了保障：只取反两个不匹配的 \(a\)，不会有元素落单。
下文记从前往后第 \(i\) 个与 \(b\) 不匹配的 \(a\) 的下标为 \(d_i\)。
确定实现方法
发现 \(\sum n\le 5\times 10^3\)，确定算法复杂度为 \(O(n^2)\)。
首先不难想到暴力搜索，每次枚举将哪一对 \((d_i, d_j)\) 取反。
亦或是使用 bitset 记录哪些非匹配值已被取反（被取反为
\(1\)，否则为 \(0\)），枚举数对暴力 DP 更新最小值。
但以上两种方法铁定超时。
受到上面两种方法的启发，扩展思维，我们发现：
取反操作的顺序不会影响最终答案。
因为每个数被取反的次数一定，最终结果也就一定。
我们可以通过 DP 的方式寻找最小值。
设计状态。
不妨考虑让问题麻烦起来的是什么，对于 \(d_i\) 与 \(d_j\) 不相邻时的取反，我们无法得知 \(d_i\) 需要哪一个 \(d_j\)（而对于 \(d_i\) 与 \(d_j\) 相邻的情况，\(d_j\) 就是 \(d_{i + 1}\)，位置是确定的）。
但我们同时也发现，与相邻时的代价不同，不相邻时的操作代价与 \(i\)，\(j\) 的具体值无关。
所以不妨用 \(f_{i,j}\) 表示，已枚举到 \(d_i\)，前面有 \(j\) 个数需要后面 与它们不相邻的数 用以和它们配对取反。
假设已枚举到 \(d_i\)，当前面有 \(s\) 个数需要配对时，有以下的情况：
当 \(s = 1\)，即只有一个数需要配对时：
如果这个数是 \(d_{i - 1}\)，那么代价为 \(2\times y\)。
注意，这里只枚举了需要不相邻的数来配对的情况，相邻的情况将会另外计算，所以代价不能为 \(x\)。
否则，代价为 \(y\)。
当 \(s>1\) 时，即有多个数需要配对时：
不管 \(d_{i-1}\) 是否需要配对，我们都不选它。因为选它的代价是 \(2\times y\)，而随便选另一个待配对数的代价都只有 \(y\)。
那么问题来了，我咋知道它们相不相邻？
再多开一维 \(0/1\) 状态，记录最后一个需要与其他后面的元素配对值是否是 \(a_{i-1}\) 即可。
假设现在已经枚举到 \(f_{i,j,0/1}\)，即已枚举完 \(d_i\)，有 \(j\) 个元素需要配对。
则更新 \(d_{i+1}\) 的状态：
若我们想要让 \(d_{i+1}\) 与后面的元素配对，则代价至少为 \(y\)。至于是否会因为待配对元素相邻而额外增加 \(y\) 的代价，我们在待配对元素处计算。
\[ f_{i+1,j+1,1}\gets\min(f_{i,j,0},f_{i,j,1}) + y \]
若我们想要让 \(d_{i+1}\) 与其相邻的 \(a_{i+2}\) 匹配，那么 \(d_{i+2}\) 就不需要再与后面的元素配对了，故最后一维为 \(0\)。
\[ f_{i+2,j,0}\gets\min(f_{i,j,0},f_{i,j,1})+(d_{i+2}-d_{i+1})\times x \]
如果我们想让 \(d_{i+1}\) 与前面的待配对元素配对：
在此种大前提下，\(d_{i+1}\) 一定不需要与后面的元素配对，故最后一维为 \(0\)。
当 \(j=1\) 且 \(d_i+1=d_{i+1}\) 时，即存在其相邻元素，且只有一个配对可选项时：
- 如果这个数是 \(d_{i}\)，则 \(d_{i+1}\) 必须与相邻元素配对。
\[ f_{i+1,j-1,0}\gets f_{i,j,1}+y \]
因为在计算 \(f_{i,j,1}\) 时已计算了一个 \(y\)，所以此处只用加一个 \(y\)。
否则，该元素完成配对，不产生任何代价。
\[ f_{i+1,j-1,0}\gets f_{i,j,0} \]
否则，随意选择前面的一个数。
因为此时，要么前面有除了相邻元素的其他数可选，要么根本没有相邻元素，所以该数完成配对不会产生任何代价（因为 \(y\) 已经加过了）。
\[ f_{i+1,j-1,0}\gets \min(f_{i,j,0},f_{i,j,1}) \]
至此，全部情况讨论完毕。因为不能让最后一个元素再去与后面的元素配对，最终答案为 \(f_{tot,0,0}\)，其中 \(tot\) 为 \(d\) 数组长度。
时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n^2)\)。
因为 \(x,y\le
10^9\)，最坏情况下需要加 \(\dfrac
n2\) 次，故需要为 DP 数组开 long long。尽管热心人士
@cqbztzl 帮助我计算得出使用空间约为 300
兆，但仍然会 MLE。
不难发现，第一维枚举到 \(i\) 时，只需要更新第一维为 \(i+1\) 和 \(i+2\) 状态的值，而不需要其他任何 DP 值，故将第一维模 \(3\)，滚动为 \(0\sim 2\)。
// 代码里可能有一些赛时的神秘注释 hhh
namespace XSC062 {
using namespace fastIO;
const ll inf = 1e18;
const int maxn = 5e3 + 5;
ll x, y;
int T, n, tot;
ll f[3][maxn][2];
int diff[maxn], a[maxn], b[maxn];
ll min(ll x, ll y) {
return x < y ? x : y;
}
void upd(int i, int j, int k, ll y) {
f[i % 3][j][k] = min(f[i % 3][j][k], y);
return;
}
int main() {
read(T);
while (T--) {
read(n), read(x), read(y);
tot = 0;
for (int i = 1; i <= n; ++i)
getnum(a[i]);
for (int i = 1; i <= n; ++i) {
getnum(b[i]);
if (a[i] != b[i])
diff[++tot] = i;
}
if (tot & 1) {
puts("-1");
continue;
}
memset(f, 0x3f, sizeof (f));
f[0][0][0] = 0;
for (int i = 0; i <= tot; ++i) {
for (int j = 0; j <= i; ++j) {
// 新增起点
if (i + 1 <= tot) {
upd(i + 1, j + 1, 1,
min(f[i % 3][j][0],
f[i % 3][j][1]) + y);
}
// 碾过去
if (i + 2 <= tot) {
upd(i + 2, j, 0,
min(f[i % 3][j][0],
f[i % 3][j][1]) +
(diff[i + 2] -
diff[i + 1]) * x);
}
// 使用起点
if (j > 0 && i + 1 <= tot) {
if (j == 1 && diff[i] + 1 ==
diff[i + 1]) {
upd(i + 1, j - 1, 0,
f[i % 3][j][1] + y);
upd(i + 1, j - 1, 0,
f[i % 3][j][0]);
}
else {
upd(i + 1, j - 1, 0,
min(f[i % 3][j][0],
f[i % 3][j][1]));
}
}
if (i != tot) {
f[i % 3][j][0] =
f[i % 3][j][1] = inf;
}
}
}
print(f[tot % 3][0][0], '\n');
}
return 0;
}
} // namespace XSC062