树状数组

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

去微博看该题解


去天涯论坛看该题解


代码

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

  

题解

  我们用dp[i][j]代表枚举到A类别的第i个任务,与B连串的第j个职分相称,所获取的最大成效,那样明显是要晚点的,可是不要紧去商讨一下。

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

  于是我们又发现多少个厉害的东西:

  一.
是因为每一个数字连出的边最三唯有玖种景况(
abs(A[i]-B[j])<=四),所以转移的复杂度大概舍去。

  二.
我们发现其实这么些事物可以用线段树来敬爱最大值(当前树状数组也足以的),那么时间复杂度就降成O(n*九log
n)的了。然则线段树的常数太大,被卡了,所以大家用树状数组就可以了。


题意回顾

  有内外两行长度为 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]间可以连一条边。现求在边与边不相交的气象下的最阿比让边数量。


题目传送门 – BZOJ49玖叁


难题传送门 – BZOJ4990


欢迎访问~原来的文章出处——博客园-zhouzhendong

 代码

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

  

题解

  我们用dp[i][j]意味着枚举到A体系的第i个岗位,与B连串的第j个任务相称,所获取的最大成效,那样显明是要过期的,不过不要紧去思考一下。

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

  于是我们又发现多个厉害的事物:

  1.
是因为每二个数字连出的边最多只有玖种情形(
abs(A[i]-B[j])<=四),所以转移的复杂度大约舍去。

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