首先将 $a_i$ 全都模 $2$。然后发现交换等价与将一个 $0$ 变 $1$，另一个 $1$ 变 $0$。

已经考虑前 $i$ 数，$0$ 变 $1$ 的次数减去 $1$ 变 $0$ 的次数，差记为 $j$，现在的 $S$ 记为 $k$，当前的前缀和记为 $b$。然后分当前这个位置的数是否变换转移。

答案就是 $f_{n, 0, k, 0/1}, k \le n$。这个思路有问题吗/kk如果没问题有没有人帮忙看一下代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define gc getchar
#define pc putchar
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )

using namespace std;

const int N = 110;
const int INF = 1e13;
const int mod = 998244353; int T = 1;
void read() { return; } template <typename T, typename ...T2> void read(T &s, T2 &...oth) { s = 0; char ch = gc(); bool f = 0; for (; ch < '0' or ch > '9'; ch = gc()) if (ch == '-') f = 1; for (; ch >= '0' and ch <= '9'; ch = gc()) s = (s << 1) + (s << 3) + (ch ^ 48); s = f ? -s : s; read(oth...); return; }
void write(char ch) { return; } template <typename T, typename ...T2> void write(char ch, T s, T2 ...oth) { if (!s) { pc('0'); pc(ch); write(ch, oth...); return; } int stk[100], top = 0; if (s < 0) pc('-'), s = ~s + 1; while (s) stk[ ++ top] = s % 10, s /= 10; do pc(stk[top -- ] + (1 << 4) + (1 << 5)); while (top); pc(ch); write(ch, oth...); return; }
int qpow(int a, int b = mod - 2, int s = 1) { for (; b; b >>= 1, a = a * a % mod) if (b & 1) s = s * a % mod; return s; }
int f[N][N * 2][N][2], n, a[N], c[N];
signed main() {
	read(T);
	while (T -- ) {
		read(n); rep(i, 1, n) read(a[i]);
		rep(i, 1, n) read(c[i]); int B = n + 1;
		rep(i, 1, n) a[i] = a[i] & 1;
		rep(i, 0, n) rep(j, -n, n) rep(k, 0, n)
			f[i][j + B][k][0] = f[i][j + B][k][1] = INF;
		f[0][B][0][0] = 0;
		rep(i, 1, n) rep(j, 1 - i, i - 1) rep(k, 0, i) rep(b, 0, 1) {
			auto v = b ^ a[i], w = k + v;
			f[i][j + B][w][v] = min(f[i][j + B][w][v], f[i - 1][j + B][k][b]);
			v = b ^ (a[i] ^ 1), w = k + v; auto &t = f[i][j + (v == 0 ? -1 : 1) + B][w][v];
			t = min(t, f[i - 1][j + B][k][b] + c[i]);
		} rep(k, 0, n) {
			int ans = min(f[n][B][k][0], f[n][B][k][1]);
			printf("%lld ", ans == INF ? -1ll : ans);
		} puts("");
	} return 0;
}