Solution to CF1733D2 Zero-One (Hard Version)。
没做过简单版本，模拟赛上遇到，乍一看是个贪心，但贪心思维太弱想不到怎么贪。所以思考其他方法。
下文称同时取反 ai 和 aj 的一次操作为「取反 (ai,aj)」，称 ai=bi 的状态为「匹配」。
#思维关键点
若我们想要将 (ai,aj) 取反，我们可以怎么做？
不难发现，分 ai 与 aj 相邻和不相邻两种情况：
ai 与 aj 相邻：
- 直接取反，代价为 x。
- 寻找到一个与 ai 和 aj 都不相邻的 ak，先将 (ai,ak) 取反，再将 (aj,ak) 取反，代价为 2×y。
ai 与 aj 不相邻：
- 直接取反，代价为 y。
- 将 (ai,ai+1),(ai+1,ai+2),⋯,(aj−1,aj) 取反，代价为 (j−i)×x。
接下来考虑另一个问题：我们要取反哪些 (ai,aj) 呢？
假设现在有 ap 与 bp 不匹配，aq 与 bq 不匹配，那么我们肯定选择将 (ap,aq) 取反。
原因很简单，假设有 ak=bk，如果我们将 (ap,ak) 取反，那么 ak≠bk，我们需要额外的一次与 ak 有关的操作将其复原。如果我们挑选一个 al=bl，并将 (ak,al) 取反，那么 al 与 bl 又会不匹配，又需要一次操作；如果挑选一个 al≠bl，并将 (ak,al) 取反，那么为什么不能在一开始就将 (ap,al) 取反呢？此时的 ak 相当于一个中继，而这种情况我们已经在取反 (ap,al) 时考虑到了。
也就是说，我们每次取反 只 选择两个无法与 b 匹配的 a。
那么，有没有一种情况，让我们无法选择两个无法匹配的值呢？
那就是不匹配的值的数量有奇数个，才会让我们两个两个选的时候有元素落单。
不妨思考一次取反操作所有可能的情况（假设不受上面的结论限制）：
取反一个匹配值和一个不匹配值
此时匹配值变为非匹配，不匹配值变为匹配，不匹配的元素总数不变。取反两个不匹配值
两个不匹配值都变为匹配，不匹配元素的总数量增加 −2。取反两个匹配值
两个匹配值都变为非匹配，不匹配元素的总数量增加 2。
综上，一次操作对不匹配元素总数带来的更改只可能为 0,2,−2，均为偶数。当不匹配元素为奇数时，必定无法将其更改至刚好为 0。此时输出 −1。
我们上面结论的可实现性也得到了保障：只取反两个不匹配的 a，不会有元素落单。
下文记从前往后第 i 个与 b 不匹配的 a 的下标为 di。
#确定实现方法
发现 ∑n≤5×103，确定算法复杂度为 O(n2)。
首先不难想到暴力搜索，每次枚举将哪一对 (di,dj) 取反。
亦或是使用 bitset 记录哪些非匹配值已被取反（被取反为 1，否则为 0），枚举数对暴力 DP 更新最小值。
但以上两种方法铁定超时。
受到上面两种方法的启发，扩展思维，我们发现：
取反操作的顺序不会影响最终答案。
因为每个数被取反的次数一定，最终结果也就一定。我们可以通过 DP 的方式寻找最小值。
设计状态。
不妨考虑让问题麻烦起来的是什么，对于 di 与 dj 不相邻时的取反，我们无法得知 di 需要哪一个 dj（而对于 di 与 dj 相邻的情况，dj 就是 di+1，位置是确定的）。
但我们同时也发现，与相邻时的代价不同，不相邻时的操作代价与 i，j 的具体值无关。
所以不妨用 fi,j 表示，已枚举到 di，前面有 j 个数需要后面 与它们不相邻的数 用以和它们配对取反。
假设已枚举到 di，当前面有 s 个数需要配对时，有以下的情况：
当 s=1，即只有一个数需要配对时：
如果这个数是 di−1，那么代价为 2×y。
注意，这里只枚举了需要不相邻的数来配对的情况，相邻的情况将会另外计算，所以代价不能为 x。- 否则，代价为 y。
当 s>1 时，即有多个数需要配对时：
不管 di−1 是否需要配对，我们都不选它。因为选它的代价是 2×y，而随便选另一个待配对数的代价都只有 y。
那么问题来了，我咋知道它们相不相邻？
再多开一维 0/1 状态，记录最后一个需要与其他后面的元素配对值是否是 ai−1 即可。
假设现在已经枚举到 fi,j,0/1，即已枚举完 di，有 j 个元素需要配对。
则更新 di+1 的状态：
若我们想要让 di+1 与后面的元素配对，则代价至少为 y。至于是否会因为待配对元素相邻而额外增加 y 的代价，我们在待配对元素处计算。
fi+1,j+1,1←min(fi,j,0,fi,j,1)+y若我们想要让 di+1 与其相邻的 ai+2 匹配，那么 di+2 就不需要再与后面的元素配对了，故最后一维为 0。
fi+2,j,0←min(fi,j,0,fi,j,1)+(di+2−di+1)×x如果我们想让 di+1 与前面的待配对元素配对：
在此种大前提下，di+1 一定不需要与后面的元素配对，故最后一维为 0。
当 j=1 且 di+1=di+1 时，即存在其相邻元素，且只有一个配对可选项时：
- 如果这个数是 di，则 di+1 必须与相邻元素配对。
fi+1,j−1,0←fi,j,1+y
因为在计算 fi,j,1 时已计算了一个 y，所以此处只用加一个 y。否则，该元素完成配对，不产生任何代价。
fi+1,j−1,0←fi,j,0
否则，随意选择前面的一个数。
因为此时，要么前面有除了相邻元素的其他数可选，要么根本没有相邻元素，所以该数完成配对不会产生任何代价（因为 y 已经加过了）。
fi+1,j−1,0←min(fi,j,0,fi,j,1)
至此，全部情况讨论完毕。因为不能让最后一个元素再去与后面的元素配对，最终答案为 ftot,0,0，其中 tot 为 d 数组长度。
时间复杂度 O(n2)，空间复杂度 O(n2)。
因为 x,y≤109，最坏情况下需要加 n2 次，故需要为 DP 数组开 long long。尽管热心人士 @cqbztzl 帮助我计算得出使用空间约为 300 兆，但仍然会 MLE。
不难发现，第一维枚举到 i 时，只需要更新第一维为 i+1 和 i+2 状态的值，而不需要其他任何 DP 值，故将第一维模 3，滚动为 0∼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