专栏文章

题解：P6820 [PA 2012 Finals] Two Cakes

IIstruggle
P6820题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minpmydr
此快照首次捕获于
2025/12/02 06:17
3 个月前
此快照最后确认于
2025/12/02 06:17
3 个月前
查看原文
看了很久才看明白是怎么优化到一维的，所以写了这篇题解。
设 fx,yf_{x,y} 表示第一个序列写到 axa_x ,第二个序列写道 byb_y 时的答案，朴素转移方程为:
当 ax=aya_x = a_y 时 :fx,y=min⁡{fx−1,y,fx,y−1}+1 f_{x,y}=\min\{f_{x-1,y},f_{x,y-1}\}+1
否则 :fx,y=fx−1,y−1+1f_{x,y}=f_{x-1,y-1} + 1。
令 gx,y=fx,y−xg_{x,y} = f_{x,y} - x
那么: fx−1,y−x=(fx−1,y−(x−1))−1=gx−1,y−1f_{x-1,y} - x = (f_{x-1,y}-(x-1))-1=g_{x-1,y}-1 fx,y−1−x=gx,y−1f_{x,y-1}-x=g_{x,y-1}
所以对于第一种转移 gx,y=min⁡{gx−1,y−1,gx,y−1}+1=min⁡{gx−1,y,gx,y−1+1}g_{x,y} = \min\{g_{x-1,y}-1,g_{x,y-1}\}+1=\min\{g_{x-1,y},g_{x,y-1}+1\} 对于第二种转移 gx,y=fx−1,y−1+1−x=fx−1,y−1−(x−1)+(x−1+1−x)=gx−1,y−1g_{x,y}=f_{x-1,y-1}+1-x = f_{x-1,y-1}-(x-1)+(x-1+1-x) = g_{x-1,y-1} 这就意味着，对于 ax≠bya_x \ne b_y 的位置，gx,yg_{x,y} 的值不会改变，这样在转移时就不用在意。
由于 gx,y=fx,y−xg_{x,y} = f_{x,y} - x 所以答案需要加上 xx。 接着，为了压缩为一维，我们需要找到一种对于 (x,y)(x,y) 的一种映射方式，例如下面代码中将 (x,y)(x,y) 映射为 (n−x+y)(n-x+y)， 因为这样映射只有差值相同映射值才会相同，而由前面的结论可知，差值相同时 gx,yg_{x,y} 的值相同，所以这种映射是正确的。
代码中的 fx,yf_{x,y} 对应题解中的 gx,yg_{x,y}。
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,a[N],p[N],f[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){int x; scanf("%d",&x); p[x]=i;}
	for(int i=n;i<=2*n;i++) f[i]=i-n;
	for(int i=1;i<=n;i++){
		f[p[a[i]]+n-i]=min(f[p[a[i]]+n-i+1],f[p[a[i]]+n-i-1]+1);
	}
    printf("%d\n",f[n]+n);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...