本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-10 21:17:08

前言

:::epigraph[] 只有我赛时写的 Trie 树优化转移，然后卡了一年的常吗？ :::

状态定义的方式不同，转移优化的难度和时间复杂度是不同的。这个还是第一次见，感觉挺深刻的。

:::info[题目描述] 给定两个长度为 $n$ 的非负整数序列 $a,b$。接下来进行若干次操作：

• 选择一个整数 $x\in[1,n]$ 与一个正整数 $y$。
• 进行操作 $\forall i\in[1,x],a_i\gets a_i\oplus y$。即将 $[1,x]$ 中数异或上 $y$。
• 这次操作的代价为 $b_x$。

输出通过若干次操作使得 $a$ 变为单调不降的最小代价。 :::

思路

不难想到用 DP 求解。由于每次是将前缀异或，所以倒着做会比较方便（应该正着做也行，没细想）。

需要观察到答案分为两种情况：

1. $a_n$ 不操作：任何时刻，后缀操作的异或和不会超过 $V$。
2. $a_n$ 操作：最优异或 $2^{10000}+x$，其中 $x$ 为任意不超过 $V$ 的非负整数。一旦某个位置要操作，只需要将 $2$ 的指数次幂减少 $1$，并随意改动 $x$。

情况 1（$a_n$ 不操作）

令 $f_{i,j}$ 表示 $i\sim n$ 位置中，所有位置的操作的异或和为 $j$。这时候，如果 $i$ 位置操作为异或 $k$，则需满足 $a_i\oplus k\oplus j\le a_{i+1}\oplus j$。所有合法的 $k$ 是 Trie 树上 $\log V$ 个子树。这样，复杂度即可做到 $O(nV\log V)$。

不过，这样太不好了。我们将限制放在转移中，但实际上可以将限制放在状态里。即，令 $f_{i,j}$ 表示 $i\sim n$ 位置中，$a_i$ 最终的值为 $j$。如果操作，则 $a_{i}$ 可以变成任何值。这样，转移只需要做后缀 $\max$ 即可（也就是转化成了一段区间）。

时间复杂度：$O(nV)$。

情况 2（$a_n$ 操作）

根据上述分析，只要操作，异或值可以变成任何值。于是，令 $f_{i,j}$ 表示 $i\sim n$ 位置，所有操作的异或和为 $j$。转移是容易做到 $O(1)$ 的。

时间复杂度：$O(nV)$。

代码

:::success[赛时代码 $O(nV\log V)$]

#include <bits\/stdc++.h>
using namespace std;
using i64 = long long;

int n;
int a[1 << 13], b[1 << 13];
i64 dp[2][1 << 13], fg[13][1 << 13];

inline void chmin(i64 &a, i64 b) { a = min(a, b); }
void solve() {
	cin >> n;
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	for (int i = 1; i <= n; i ++)
		cin >> b[i];

	memset(dp, 0x3f, sizeof dp);
	dp[n & 1][0] = 0;
	for (int i = n - 1; i >= 1; i --) {
		memset(dp[i & 1], 0x3f, sizeof dp[i & 1]);
		memset(fg, 0x3f, sizeof fg);
		for (int j = 0; j < 1 << 13; j ++) {
			if (dp[~i & 1][j] >= 1E18) continue;
			int x = a[i] ^ j, y = a[i + 1] ^ j;
			int S = j;
			for (int k = 12; k >= 0; k --)
				if (y >> k & 1) {
					chmin(fg[k][(S ^ ((x >> k & 1) << k)) >> k], dp[~i & 1][j]);
					S ^= (~x >> k & 1) << k;
				} else if (x >> k & 1) S ^= 1 << k;
			fg[0][S] = min(fg[0][S], dp[~i & 1][j]);
			if (x <= y)
				dp[i & 1][j] = min(dp[i & 1][j], dp[~i & 1][j]);
		}
		for (int k = 12; k >= 0; k --)
			for (int x = 0; x < 1 << 13 - k; x ++)
				if (fg[k][x] < 1E18)
					for (int y = 0; y < 1 << k; y ++)
						dp[i & 1][x << k | y] = min(dp[i & 1][x << k | y], fg[k][x] + b[i]);
	}
	i64 res = 1ll << 60;
	for (int i = 0; i < 1 << 13; i ++)
		res = min(res, dp[1][i]);

	for (int i = 0; i < 1 << 13; i ++)
		dp[n & 1][i] = b[n];
	for (int i = n - 1; i >= 1; i --) {
		i64 mn = 1ll << 60;
		for (int j = 0; j < 1 << 13; j ++)
			mn = min(mn, dp[~i & 1][j]);
		for (int j = 0; j < 1 << 13; j ++) {
			dp[i & 1][j] = mn + b[i];
			if ((a[i] ^ j) <= (a[i + 1] ^ j))
				dp[i & 1][j] = min(dp[i & 1][j], dp[~i & 1][j]);
		}
	}
	for (int i = 0; i < 1 << 13; i ++)
		res = min(res, dp[1][i]);

	cout << res << '\n';
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int T;
	cin >> T;

	while (T -- ) solve();

	return 0;
}

:::

:::success[$O(nV)$ 代码]{open}

void solve() {
	cin >> n;
	int mx = 0;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], mx = max(mx, a[i]);
	for (int i = 1; i <= n; i ++)
		cin >> b[i];
	mx = (1 << __lg(mx) + 1);

	memset(dp, 0x3f, sizeof dp);
	dp[n & 1][a[n]] = 0;
	for (int i = n - 1; i >= 1; i --) {
		memset(dp[i & 1], 0x3f, sizeof dp[i & 1]);
		i64 mn = 1ll << 60;
		for (int j = mx - 1; j >= 0; j --) {
			int k = a[i] ^ j ^ a[i + 1];
			if (k <= j) dp[i & 1][k] = min(dp[i & 1][k], dp[~i & 1][j]);
			mn = min(mn, dp[~i & 1][j]);
			dp[i & 1][j] = min(dp[i & 1][j], mn + b[i]);
		}
	}
	i64 res = 1ll << 60;
	for (int i = 0; i < mx; i ++)
		res = min(res, dp[1][i]);

	for (int i = 0; i < mx; i ++)
		dp[n & 1][i] = b[n];
	for (int i = n - 1; i >= 1; i --) {
		i64 mn = 1ll << 60;
		for (int j = 0; j < mx; j ++)
			mn = min(mn, dp[~i & 1][j]);
		for (int j = 0; j < mx; j ++) {
			dp[i & 1][j] = mn + b[i];
			if ((a[i] ^ j) <= (a[i + 1] ^ j))
				dp[i & 1][j] = min(dp[i & 1][j], dp[~i & 1][j]);
		}
	}
	for (int i = 0; i < mx; i ++)
		res = min(res, dp[1][i]);

	cout << res << '\n';
}

:::