题解：P6820 [PA 2012 Finals] Two Cakes

joe_zxq · 2025-10-28 20:32:52 · 题解

蓝色的思维题能不能去死啊。

首先考虑 \mathcal O(N^2) 的暴力。定义 dp_{i,j} 表示到了 A 的第 i 位，B 的第 j 位时的最小时间。

有递推式如下：

考虑优化。由于 A,B 都是排列，所以 A_i=B_j 最多出现 N 次，可以记忆化搜索。又注意到 A_i \neq B_j 的转移实则就是平移，于是考虑将这种情况转移到前面最近的 A_i=B_j 的位置即可，可以通过二分进行实现。

二分查找位置的方法：由于平移时 i-j 是不变的，所以预处理出对于每个 d，所有 i-j=d 的 A_i=B_j 的位置，然后排序即可。

:::info[正解代码]

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll N = 1e6 + 5;
ll n, a[N], b[N], pos[N], dp[N];
vector<ll> vec[N << 1];

ll dfs(ll i, ll j) {
    if (a[i] == b[j]) {
        if (dp[i] != -1) {
            return dp[i];
        }
        return dp[i] = min(dfs(i - 1, j), dfs(i, j - 1)) + 1;
    }
    ll d = i - j + n;
    ll p = lower_bound(vec[d].begin(), vec[d].end(), i) - vec[d].begin() - 1;
    if (p == -1) {
        return max(i, j);
    }
    p = vec[d][p];
    return dfs(p, j - (i - p)) + i - p;
}

void solve() {
    memset(dp, -1, sizeof dp);
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        pos[a[i]] = i;
    }
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", &b[i]);
        vec[pos[b[i]] - i + n].push_back(pos[b[i]]);
    }
    cout << dfs(n, n) << "\n";
}

int main() {
    solve();
    return 0;
}

:::