洛谷 P3657 [USACO17FEB]Why Did the Cow Cross the Road II P

大意：让你把两个n的排列做匹配，连线不想交，而且匹配的数字的差<=4，求最大匹配数

sol：（参考了kczno1的题解）对于第一个排列从左往右枚举，用树状数组维护到达另一个序列第i个数字的最大值。

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=;

int n,a[N],b[N],f[N],t[N];

#define lowbit(x) ((x)&(-x))

inline void ins(int x,int v){for(;x<=n;x+=lowbit(x)){if(t[x]>v)break;t[x]=v;}}

inline int que(int x){int re=; for(;x;x-=lowbit(x))re=max(re,t[x]);return re;}

int main()

{

    int i,j,x; scanf("%d",&n);for(i=;i<=n;i++)scanf("%d",&a[i]);for(i=;i<=n;i++)scanf("%d",&x),b[x]=i;

    for(i=;i<=n;i++)

    {

        for(j=max(,a[i]-);j<=min(n,a[i]+);j++)f[j]=que(b[j]-);

        for(j=max(,a[i]-);j<=min(n,a[i]+);j++)ins(b[j],f[j]+);

    }printf("%d\n",que(n));

}

--------------------分割线-下方无关----------------

大概是受了大佬的启发，我水掉了一个留了半年多的大坑（最长公共子序列的模板）直接贴链接和代码吧

题面

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=;

int n,a[N],b[N],f[N],t[N];

#define lowbit(x) ((x)&(-x))

inline void ins(int x,int v){for(;x<=n;x+=lowbit(x)){if(t[x]>v)break;t[x]=v;}}

inline int que(int x){int re=; for(;x;x-=lowbit(x))re=max(re,t[x]);return re;}

int main()

{

    int i,x; scanf("%d",&n); for(i=;i<=n;i++)scanf("%d",&a[i]); for(i=;i<=n;i++)scanf("%d",&x),b[x]=i;

    for(i=;i<=n;i++)

    {

        f[a[i]]=que(b[a[i]]-); ins(b[a[i]],f[a[i]]+);

    }printf("%d\n",que(n));

}

巴特西

洛谷 P3657 [USACO17FEB]Why Did the Cow Cross the Road II P

最新文章

热门文章