题解：P6820 [PA 2012 Finals] Two Cakes

· · 题解

看了很久才看明白是怎么优化到一维的，所以写了这篇题解。

设 f_{x,y} 表示第一个序列写到 a_x ,第二个序列写道 b_y 时的答案，朴素转移方程为:

当 a_x = a_y 时 : f_{x,y}=\min\{f_{x-1,y},f_{x,y-1}\}+1\ 否则 :f_{x,y}=f_{x-1,y-1} + 1。

令 g_{x,y} = f_{x,y} - x
那么:

f_{x-1,y} - x = (f_{x-1,y}-(x-1))-1=g_{x-1,y}-1 f_{x,y-1}-x=g_{x,y-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\}

对于第二种转移

g_{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}

这就意味着，对于 a_x \ne b_y 的位置，g_{x,y} 的值不会改变，这样在转移时就不用在意。

由于 g_{x,y} = f_{x,y} - x 所以答案需要加上 x。 接着，为了压缩为一维，我们需要找到一种对于 (x,y) 的一种映射方式，例如下面代码中将 (x,y) 映射为 (n-x+y)， 因为这样映射只有差值相同映射值才会相同，而由前面的结论可知，差值相同时 g_{x,y} 的值相同，所以这种映射是正确的。

代码中的 f_{x,y} 对应题解中的 g_{x,y}。

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