自动搬运

查看原文

来自洛谷，原作者为

	cancan123456 怄火。挥手。转圈。街舞。跳跳。献吻。跳绳。激动。发抖。磕头。爱情。飞吻。左太极。右太极。回头。

搬运于2025-08-24 23:00:33，当前版本为作者最后更新于2024-07-07 22:26:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先将 $a_i$ 变为 $a_i\bmod 2$，注意到我们不会交换两个相同的 $a_i$，只会交换 $0$ 和 $1$，且同一个位置不会被交换两次。

因此考虑将一次交换看成两次切换：$0\to1,1\to0$，且将 $a_i$ 切换需要 $c_i$ 的代价。

容易发现如果 $a_i$ 中 $1$ 的数量如果与操作后 $a_i'$ 中 $1$ 的数量相同，则总可以构造出一种交换方案能够将 $a_i$ 变为 $a_i'$，因此这种考虑是符合题意的。

现在设计 DP 状态：$f_{i,j,k}$ 表示考虑了 $a$ 长度为 $i$ 的前缀，已经得到了 $j$ 个 $1$，且前缀和序列 $b$ 的前 $i$ 项有 $k$ 个 $1$ 的最小花费。

初始状态显然为 $f_{0,0,0}=0$，其余状态全部为正无穷。

考虑从 $f_{i,j,k}$ 转移，设操作后 $a_{i+1}'=l$，其中 $0\le l\le1$，则有转移：

$$f_{i+1,j+l,(j+l)\bmod 2+k}\gets f_{i,j,k}+c_{i+1}[a_{i+1}\ne l] $$

求答案时，需要保证 $a_i'$ 中的 $1$ 数量等于 $a$ 中的 $1$ 数量 $t$，因此答案为 $f_{n,t,S}$，输出即可。

时间复杂度为 $O(n^3)$，可以通过此题，以下为赛时代码。

#include <cstdio>
using namespace std;
const int N = 505;
int a[N], c[N], f[N][N][N];
int min(int a, int b) {
	return a < b ? a : b;
}
int main() {
	int T;
	scanf("%d", &T);
	for (int n; T != 0; T--) {
		scanf("%d", &n);
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			a[i] %= 2;
			cnt += a[i];
		}
		for (int i = 1; i <= n; i++) {
			scanf("%d", &c[i]);
		}
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				for (int k = 0; k <= n; k++) {
					f[i][j][k] = 0x3f3f3f3f;
				}
			}
		}
		// f[i][j][k] 为前 i 个数中 a[x] = 1 有 j 个，b 中 1 的个数为 k 的最小代价.
		f[0][0][0] = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= n; j++) {
				for (int k = 0; k <= n; k++) {
					if (f[i][j][k] != 0x3f3f3f3f) {
						for (int l = 0; l <= 1; l++) {
							int & to = f[i + 1][j + l][k + (j + l) % 2];
							to = min(to, f[i][j][k] + c[i + 1] * (a[i + 1] ^ l));
						}
					}
				}
			}
		}
		for (int i = 0; i <= n; i++) {
			if (f[n][cnt][i] != 0x3f3f3f3f) {
				printf("%d ", f[n][cnt][i]);
			} else {
				printf("-1 ");
			}
		}
		printf("\n");
	}
	return 0;
}