[PA2012]Dwa torty

[PA2012]Dwa torty

题目大意：

给定两个排列(A_{1sim n},B_{1sim n})，你需要将两个排列用最少的次数消除。

消除只能从头消除，一次消除可以从两个排列的头部取两个不同的数消去，或者从一个排列头部取一个数消去。

问最少的消除次数。

(nle10^6)

思路：

(f[i][j])表示已经取了(A_{1sim i})和(B_{1sim j})所需的最小代价。

(A_i=B_j)时，(f[i][j]=min(f[i-1][j],f[j-1][i])+1)。

(A_i e B_j)时，令(t)为使得(A_{i-t}=B_{j-t})的最小的(t)，则(f[i][j]=f[i-t][j-t]+t)。

将(A_i=B_j)的状态进行记忆化，(A_i e B_j)的状态可以在(mathcal O(log n))的时间内转移到(A_i=B_j)的状态。

(A_i=B_j)的状态总共有(n)个，则至多需要(2n)个(A_i e B_j)的状态。因此时间复杂度(mathcal O(nlog n))。

源代码：

#include<set>
#include<cstdio>
#include<cctype>
inline int getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
const int N=1e6+1;
int a[N],b[N],p[N],f[N];
std::set<std::pair<int,int>> set;
int dp(const int &p,const int &q) {
	if(!p||!q) return p+q;
	if(a[p]==b[q]) return f[p]=f[p]?:std::min(dp(p,q-1),dp(p-1,q))+1;
	const auto k=std::prev(set.upper_bound(std::make_pair(p-q,p)));
	if(k->first!=p-q) return std::max(p,q);
	const int r=k->second;
	return dp(r,r-p+q)+p-r;
}
int main() {
	const int n=getint();
	for(register int i=1;i<=n;i++) a[i]=getint();
	for(register int i=1;i<=n;i++) b[i]=getint();
	for(register int i=1;i<=n;i++) p[a[i]]=i;
	set.insert(std::make_pair(-n,0));
	for(register int i=0;i<=n;i++) {
		set.insert(std::make_pair(p[b[i]]-i,p[b[i]]));
	}
	printf("%d
",dp(n,n));
	return 0;
}