6820 [PA2012]Two Cakes

zhqwq · 2020-09-21 21:56:23 · 个人记录

曹队是我们的红太阳！我们要矢志不渝跟着曹队走！！！

然后你可以发现f[i-1][j-1]<=f[i-1][j],f[i-1][j-1]<=f[i][j-1]这样。（不可能匹配多了花费还少了啊。。。）

那i!=j就成了f[i][j]=f[i-1][j-1]+1~~~~ a_i!=b_j

如果a_{i-1}!=b_{j-1}，那可以以此类推，所以最后花费成了：

那么就是f[i][j]=f[i-t][j-t]+t，其中t是最小的使得a_{i-t}=b_{j-t}的数。

然后开始神乎其技地优化状态了：

由于是个排列，所以a_i==b_j的只有n个状态。

而a_i!=b_j的可以迅速找到上一个a_i==b_j的位置，然后直接算出。

所以我们只需要算那“n个状态的答案”即可，需要哪个dp值直接算。

如何迅速找？开个g数组维护一下即可。

//抄代码带师

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using std::max;
using std::min;

const int MAXN=1001000;
int n;
int a[MAXN],b[MAXN];
int pos[MAXN];
int F[MAXN];//F[i]表示，找和i颜色一样的j，即f[i][j]
int G[MAXN<<1];//最靠后的<i,j> 

int get_f(int i,int j){
    if(!G[j-i+1+n])return max(i,j);
    return F[G[j-i+1+n]]+i-G[j-i+1+n]; 
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)pos[b[i]]=i;
    for(int i=1;i<=n;i++){
        int j=pos[a[i]];
        F[i]=min(get_f(i,j-1)+1,get_f(i-1,j)+1);
        G[j-i+1+n]=i;
    }
    printf("%d\n",get_f(n,n));
    return 0;
}