题解 P3657 【[USACO17FEB]Why Did the Cow Cross the Road II P】

kczno1 · 2017-06-07 09:52:57 · 题解

题意(我没读懂，感谢__stdcall):

让你把两组数字做匹配，连线不相交，并且匹配的每组数字相差<=4。

求最大匹配数。

题解:

从左到右枚举第一行的数，维护第二行每个位置结尾的最大匹配值的前缀max。

就是枚举他能匹配的位置并修改，用树状数组维护。

时间O(nlogn)

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=1;i<=n;++i)
#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'0');
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}

const int N=1e5+5;
int n,a[N],dy[N],now[N];

int c[N];
int qiu(int i)
{
    int ans=0;
    for(;i;i-=i&-i)if(c[i]>ans)ans=c[i];
    return ans;
}
void add(int i,int x)
{
    for(;i<=n;i+=i&-i)
    {
        if(c[i]>=x)return ;
        c[i]=x;
    }
}

int main()
{
    freopen("1.in","r",stdin);
    n=read();
    rep(i,n)a[i]=read();
    rep(i,n)dy[read()]=i;
    rep(i,n)
    {
        int x=a[i];
        for(int j=max(1,x-4);j<=min(n,x+4);++j)now[j]=qiu(dy[j]-1);
        for(int j=max(1,x-4);j<=min(n,x+4);++j)add(dy[j],now[j]+1);
    }
    printf("%d\n",qiu(n));
}