【牛客网】Longest Common Subsequence

发现只有d数组最格路

于是我们把前三个数组中相同的数记成一个三维坐标，同一个数坐标不会超过8个

从前往后枚举d，每次最多只会更新不超过8个点

而每个点更新就是找这个点三维偏序都小于它的最大的一个值+1来更新它

用KD树来维护，这个点与树中节点三维的某一维不相交就退出

可以加的剪枝是如果树中最大值+1小于当前搜到的答案就退出

然后把新的值在树中进行更新

跑的还是挺快的，0.5s不到

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define ba 47

#define MAXN 10005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

    if(c == '-') f = -1;

    c = getchar();

    }

    while(c >= '0' && c <= '9') {

    res = res * 10 +c - '0';

    c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

    out(x / 10);

    }

    putchar('0' + x % 10);

}

int N,dimension;

int a[MAXN],b[MAXN],c[MAXN],d[MAXN],rt,Ncnt;

vector<int> v[3][MAXN];

struct node {

    int x,y,z;

    friend bool operator < (const node &a,const node &b) {

	if(dimension == 0) return a.x < b.x;

	else if(dimension == 1) return a.y < b.y;

	else return a.z < b.z;

    }

    friend bool operator == (const node &a,const node &b) {

	return a.x == b.x && a.y == b.y && a.z == b.z;

    }

    friend void upmin(node &a,node b) {

	a.x = min(a.x,b.x);a.y = min(a.y,b.y);a.z = min(a.z,b.z);

    }

    friend void upmax(node &a,node b) {

	a.x = max(a.x,b.x);a.y = max(a.y,b.y);a.z = max(a.z,b.z);

    }

};

struct KD_node {

    node p;int v,maxv;

    node av,bv;

    int lc,rc;

}tr[MAXN * 8];

vector<node> pos[MAXN],line;

vector<int> rec[MAXN];

bool vis[15];

#define lc(u) tr[u].lc

#define rc(u) tr[u].rc

void build(int &u,int l,int r,int d) {

    if(l > r) return;

    u = ++Ncnt;

    dimension = d;

    int mid = (l + r) >> 1;

    nth_element(line.begin() + l,line.begin() + mid,line.begin() + r + 1);

    tr[u].p = line[mid];tr[u].v = 0;tr[u].maxv = 0;

    tr[u].av = line[mid];tr[u].bv = line[mid];

    build(lc(u),l,mid - 1,(d + 1) % 3);

    build(rc(u),mid + 1,r,(d + 1) % 3);

    upmin(tr[u].av,tr[lc(u)].av);upmin(tr[u].av,tr[rc(u)].av);

    upmax(tr[u].bv,tr[lc(u)].bv);upmax(tr[u].bv,tr[rc(u)].bv);

}

bool sless(node a,node b) {

    return a.x < b.x && a.y < b.y && a.z < b.z;

}

bool uless(node a,node b) {

    return a.x <= b.x && a.y <= b.y && a.z <= b.z;

}

bool checkin(node x,int u) {

    return uless(tr[u].av,x) && uless(x,tr[u].bv);

}

void update(int u) {

    tr[u].maxv = max(tr[u].v,max(tr[lc(u)].maxv,tr[rc(u)].maxv));

}

void Change(int u,node p,int v) {

    if(!u) return;

    if(tr[u].p == p) {tr[u].v = v;update(u);return;}

    if(!checkin(p,u)) return;

    Change(lc(u),p,v);

    Change(rc(u),p,v);

    update(u);

}

int ta;

void Query(int u,node p) {

    if(tr[u].maxv + 1 <= ta) return;

    if(!sless(tr[u].av,p)) return;

    if(sless(tr[u].p,p)) ta = max(ta,tr[u].v + 1);

    Query(lc(u),p);Query(rc(u),p);

}

void Update_array(node p,int v) {

    ta = max(v,1);

    Query(1,p);

}

void Solve() {

    read(N);

    for(int i = 1 ; i <= N ; ++i) {read(a[i]);v[0][a[i]].pb(i);}

    for(int i = 1 ; i <= N ; ++i) {read(b[i]);v[1][b[i]].pb(i);}

    for(int i = 1 ; i <= N ; ++i) {read(c[i]);v[2][c[i]].pb(i);}

    for(int i = 1 ; i <= N ; ++i) read(d[i]);

    for(int i = 1 ; i <= N ; ++i) {

	for(auto t0 : v[0][i]) {

	    for(auto t1 : v[1][i]) {

		for(auto t2 : v[2][i]) {

		    pos[i].pb((node){t0,t1,t2});rec[i].pb(0);

		    line.pb((node){t0,t1,t2});

		}

	    }

	}

    }

    tr[0].av = (node){0x7fffffff,0x7fffffff,0x7fffffff};tr[0].bv = (node){-1,-1,-1};

    build(rt,0,line.size() - 1,0);

    int ans = 0;

    for(int i = 1 ; i <= N ; ++i) {

	memset(vis,0,sizeof(vis));

	for(int j = 0 ; j < pos[d[i]].size() ; ++j) {

	    Update_array(pos[d[i]][j],rec[d[i]][j]);

	    if(ta > rec[d[i]][j]) vis[j] = 1;

	    rec[d[i]][j] = ta;

	    ans = max(ans,ta);

	}

	for(int j = 0 ; j < pos[d[i]].size() ; ++j) {

	    if(vis[j]) Change(1,pos[d[i]][j],rec[d[i]][j]);

	}

    }

    out(ans);enter;

}

int main(){

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

巴特西

【牛客网】Longest Common Subsequence

【牛客网】Longest Common Subsequence

最新文章

热门文章