§ 题意简述

题面好长

大概意思就是说给你两个长度均为 $n$ 的整数序列，然后如果两个位置的值的差的绝对值小于4那么这两个位置就可以连一条边。要求边不交叉，求最多能连多少条。

§ 题解

提供一种纯树状数组的做法。（去他的dp）

选取一行作为“参考行”，然后维护能与其匹配的位置，然后树状数组修改。

树状数组的思路要比dp的LCS简洁很多。

所以我们一起放弃dp罢

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define one max(1, a[i] - 4)
#define two min(n, a[i] + 4)

using namespace std;

const int MAXN = 1e5 + 5;
int bit[MAXN], a[MAXN], t[MAXN];
int n, rnk[MAXN];

void modify(int x, int y) {
	for (; x <= n; x += x & -x)
		if (y < bit[x]) return ;
		else bit[x] = y;
}

int queryf(int x) {
	int res = 0;
	for (; x; x -= x & -x)
		res = max(res, bit[x]);
	return res;
}

signed main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for (int i = 1, x; i <= n; ++i) scanf("%d", &x), rnk[x] = i;
	for (int i = 1; i <= n; ++i) {
		for (int j = one; j <= two; ++j) t[j] = queryf(rnk[j] - 1);
		for (int j = one; j <= two; ++j) modify(rnk[j], t[j] + 1);
	}
	printf("%d\n", queryf(n));
}