题解：P6820 [PA2012] Two Cakes

考虑最朴素的 DP。设 f(i, j) 表示消除 a_{1 \dots i},b_{1 \dots j} 的代价。转移显然：

直接做是 \mathcal O(n^2) 的。考虑优化。

注意到 f(i-1,j-1) \le \min(f(i-1,j), f(i,j-1))。所以：

满足 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)。

// 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;
}