题解：P6820 [PA 2012 Finals] Two Cakes

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

首先考虑

\mathcal O(N^2)

的暴力。定义

dp_{i,j}

表示到了

A

的第

i

位，

B

的第

j

位时的最小时间。

有递推式如下：

dp_{i,j}= \begin{cases} \min(dp_{i-1,j},dp_{i,j-1})+1 \space (A_i = B_j)\\ dp_{i-1,j-1}+1 \space (A_i \neq B_j) \end{cases}

考虑优化。由于

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

的位置，然后排序即可。

正解代码

CPP

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

题解：P6820 [PA 2012 Finals] Two Cakes

文章操作

相关推荐

评论

题解：P6820 [PA 2012 Finals] Two Cakes