题解：P6820 [PA2012] Two Cakes

考虑最朴素的 DP。设 $f(i, j)$ 表示消除 $a_{1 \dots i},b_{1 \dots j}$ 的代价。转移显然：
$$
f(i, j) = \begin{cases}
\min(f(i-1,j),f(i,j-1))+1 &a_i = b_j \\
\min(f(i-1,j), f(i,j-1),f(i-1,j-1)) + 1 & a_i \ne b_j
\end{cases}
$$
直接做是 $\mathcal O(n^2)$ 的。考虑优化。

注意到 $f(i-1,j-1) \le \min(f(i-1,j), f(i,j-1))$。所以：
$$
f(i, j) = \begin{cases}
\min(f(i-1,j),f(i,j-1))+1 &a_i = b_j \\
f(i-1,j-1) + 1 & a_i \ne b_j
\end{cases}
$$
满足 $a_i = b_j$ 的状态 $f(i, j)$ 只有 $\mathcal O(n)$ 个。我们称这样的状态为特殊状态。

注意到对于非特殊状态（$a_i \ne b_j$），它一定会从 $f(i-1,j-1)$ 转移而来。如果 $f(i-1,j-1)$ 仍不是特殊状态，那么又会从 $f(i-2,j-2)$ 转移过来。发现每次用到的状态都是唯一确定的，而且**两维状态的差固定**。

这个过程会持续到 $f(i', i'+j-i)$。这是一个特殊状态（$a_{i'} = b_{i'+j-i}$），且 $i' < i$ 且 $i'$ 最大。然后 $f(i, j) = f(i', i'+j-i)+i-i'$。求这个 $i'$ 可以预处理+二分。

分析复杂度。一个特殊状态会通过两个非特殊状态转移，而一个非特殊状态会通过一个特殊状态转移。所以总复杂度是特殊状态的数量，即 $\mathcal O(n)$。

```cpp
// Problem: 
//     T541528 左右互搏术
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/T541528?contestId=214582
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// #define tests
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, a[N], b[N];
int na[N], nb[N];		// a, b 的逆
int g[N];
vector<int> pos[N * 2];		// 每种差的出现位置

int dp(int x, int y) {
	if (!x) return y;
	if (!y) return x;
	if (a[x] == b[y]) {
		if (~g[x]) return g[x];
		return g[x] = min({dp(x - 1, y - 1) + 2, dp(x, y - 1) + 1, dp(x - 1, y) + 1});
	}
  
	auto it = lower_bound(pos[x - y + N].begin(), pos[x - y + N].end(), x);
	if (it == pos[x - y + N].begin()) return max(x, y);
	it -- ;
	return dp(*it, *it + y - x) + x - *it;
}

void solve() {
	cin >> n;
	
	for (int i = 1; i <= n; ++ i ) cin >> a[i], na[a[i]] = i;
	for (int i = 1; i <= n; ++ i ) cin >> b[i], nb[b[i]] = i;
	
	for (int i = 0; i <= n; ++ i ) {
		f[0][i] = f[i][0] = i;
	}
	for (int i = 1; i <= n; ++ i ) {
		pos[na[i] - nb[i] + N].push_back(na[i]);
	}
	for (int i = 0; i < N * 2; ++ i ) {
		sort(pos[i].begin(), pos[i].end());
	}
	memset(g, -1, sizeof g);
	cout << dp(n, n) << '\n';
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T = 1;
#ifdef tests
	cin >> T;
#endif
	while (T -- ) solve();
	return 0;
}
```

正在渲染内容...