树状数组

迎接待上访问~原文出处——博客园-zhouzhendong

迎接待上访问~原来的小说出处——博客园-zhouzhendong

去乐乎看该题解


去腾讯网看该题解


主题材料传送门 – BZOJ499叁


标题传送门 – BZOJ4990


题意总结

  有内外两行长度为 n 的数字类别 A 和连串B,都以 一 到 n 的全排列,若 abs(A[i]-B[j])<=4,则 A[i]和
B[j]间能够连一条边。现求在边与边不相交的情事下的最浦那边数量。


 

题意回顾

  有上下两行长度为 n 的数字连串 A 和连串B,都以 一 到 n 的全排列,若 abs(A[i]-B[j])<=4,则 A[i]和
B[j]间能够连一条边。现求在边与边不相交的情状下的最罗安达边数量。


题解

  我们用dp[i][j]代表枚举到A种类的第i个岗位,与B体系的第j个任务相称,所获取的最大功用,那样显然是要过期的,然而无妨去考虑一下。

  dp[i][j]=max(dp[i-1][k](1<=k<=j))

  于是大家又发现三个厉害的事物:

  一.
出于每3个数字连出的边最两唯有九种意况(
abs(A[i]-B[j])<=4),所以转移的复杂度大约舍去。

  二.
大家发现其实那几个事物能够用线段树来维护最大值(当前树状数组也足以的),那么时间复杂度就降成O(n*9log
n)的了。可是线段树的常数太大,被卡了,所以大家用树状数组就足以了。


 

题解

  我们用dp[i][j]代表枚举到A体系的第i个地方,与B体系的第j个地点相称,所获得的最大功能,那样明显是要晚点的,不过不要紧去想想一下。

  dp[i][j]=max(dp[i-1][k](1<=k<=j))

  于是咱们又发现五个厉害的东西:

  壹.
出于每1个数字连出的边最三只有玖种状态(
abs(A[i]-B[j])<=肆),所以转移的复杂度大约舍去。

  2.
大家发现其实这几个事物能够用线段树来保障最大值(当前树状数组也足以的),那么时间复杂度就降成O(n*玖log
n)的了。然而线段树的常数太大,被卡了,所以我们用树状数组就可以了。


代码

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
void read(int &x){
    x=0;
    char ch=getchar();
    while (!('0'<=ch&&ch<='9'))
        ch=getchar();
    while ('0'<=ch&&ch<='9'){
        x=x*10+ch-48;
        ch=getchar();
    }
}
const int N=1e5+5;
int n,a[N],b[N],pos[N],ps[10];
int c[N];
int lb(int x){
    return x&-x;
}
void update(int x,int d){
    for (;x<=n;x+=lb(x))
        c[x]=max(c[x],d);
}
int query(int x){
    int ans=0;
    for (;x>0;x-=lb(x))
        ans=max(ans,c[x]);
    return ans;
}
int main(){
    read(n);
    for (int i=1;i<=n;i++)
        read(a[i]);
    for (int i=1;i<=n;i++)
        read(b[i]),pos[b[i]]=i;
    memset(c,0,sizeof c);
    for (int i=1;i<=n;i++){
        int tot=0;
        for (int j=a[i]-4;j<=a[i]+4;j++)
            if (1<=j&&j<=n)
                ps[++tot]=pos[j];
        sort(ps+1,ps+tot+1);
        for (int j=tot;j>=1;j--)
            update(ps[j],query(ps[j]-1)+1);
    }
    printf("%d",query(n));
    return 0;
}

  

 代码

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
void read(int &x){
    x=0;
    char ch=getchar();
    while (!('0'<=ch&&ch<='9'))
        ch=getchar();
    while ('0'<=ch&&ch<='9'){
        x=x*10+ch-48;
        ch=getchar();
    }
}
const int N=1e5+5;
int n,a[N],b[N],pos[N],ps[10];
int c[N];
int lb(int x){
    return x&-x;
}
void update(int x,int d){
    for (;x<=n;x+=lb(x))
        c[x]=max(c[x],d);
}
int query(int x){
    int ans=0;
    for (;x>0;x-=lb(x))
        ans=max(ans,c[x]);
    return ans;
}
int main(){
    read(n);
    for (int i=1;i<=n;i++)
        read(a[i]);
    for (int i=1;i<=n;i++)
        read(b[i]),pos[b[i]]=i;
    memset(c,0,sizeof c);
    for (int i=1;i<=n;i++){
        int tot=0;
        for (int j=a[i]-4;j<=a[i]+4;j++)
            if (1<=j&&j<=n)
                ps[++tot]=pos[j];
        sort(ps+1,ps+tot+1);
        for (int j=tot;j>=1;j--)
            update(ps[j],query(ps[j]-1)+1);
    }
    printf("%d",query(n));
    return 0;
}