nkoj-7906题解

$\texttt{Description}$

略。

$\texttt{Solution}$

很神奇的好题。

对于这种题目第一眼就会想到万能的暴力状压。然后我们规定一下这些数字对排列的顺序以使其变为一般DP优化复杂度：对于两个数对 $i,j$，当且仅当 $a_i>b_j,b_i\le a_j$ 时， $i$ 必须排在 $j$ 前面。即 $a_i+a_j\le b_i+b_j$ 时，$i$ 一定能排在 $j$ 前面（但不一定必须排在 $j$ 前面）。于是把原来的数对排个序。

$dp_{i,j}$ 表示考虑到了第 $i$ 个数对。当前选择了的最小的 $a_i$ 为 $j$，最多能选多少对出来。

转移方程：

$dp_{i,a_i}=max^{\infty}_{a_i}+1$（选择第 $i$ 个数对，且 $a_i$ 为最小值）

$dp_{i,j}=dp_{i-1,j}+1(b_i< j\le a_i)$（选择第 $i$ 个数对，且之前已经出现过了比当前的 $a_i$ 更大的 $a$ 值）

否则 $dp_{i,j}=dp{i-1,j}$ （无法接上第 $i$ 个数对）

注意 $a_i\le b_i$ 时第二条转移方程不适用，且第一条方程要改为 $dp_{i,b_i+1}=max^{\infty}_{a_i}+1$

注意，上面的转移方程相对于上一个阶段，仅仅是将一段区间的状态加上了 $1$，对 $dp_{i,a_i}$ 单独计算。这样重新暴力计算这个阶段是很浪费的，用线段树维护即可。

$\texttt{Code}$

#include <cstdio>
#include <algorithm>

inline int max(const int x, const int y) {return x > y ? x : y;}
struct Node {
	int l, r, v, Lazy;
} c[800005];
void make_tree(const int O, const int L, const int R) {
	c[O].l = L, c[O].r = R;
	if (L != R) make_tree(O << 1, L, L + R >> 1), make_tree(O << 1 | 1, (L + R >> 1) + 1, R);
}
void pushdown(const int O) {
	c[O << 1].v += c[O].Lazy, c[O << 1 | 1].v += c[O].Lazy;
	c[O << 1].Lazy += c[O].Lazy, c[O << 1 | 1].Lazy += c[O].Lazy;
	c[O].Lazy = 0;
}
void update(const int O, const int L, const int R, const int d) {
	if (L <= c[O].l && c[O].r <= R) {c[O].v += d, c[O].Lazy += d; return;}
	int mid(c[O].l + c[O].r >> 1);
	pushdown(O);
	if (L <= mid) update(O << 1, L, R, d);
	if (mid < R) update(O << 1 | 1, L, R, d);
	c[O].v = max(c[O << 1].v, c[O << 1 | 1].v);
}
int query(const int O, const int L, const int R) {
	if (L <= c[O].l && c[O].r <= R) return c[O].v;
	int mid(c[O].l + c[O].r >> 1), ans(0);
	pushdown(O);
	if (L <= mid) ans = query(O << 1, L, R);
	if (mid < R) ans = max(ans, query(O << 1 | 1, L, R));
	return ans;
}
struct node {
	int a, b;
	inline bool operator < (const node X) const {return a + b > X.a + X.b;}
} a[100005];
int b[200005], A[100005], B[100005];

int main() {
	int n;
	scanf("%d", &n);
	for (int i(1); i <= n; ++ i) scanf("%d%d", &a[i].a, &a[i].b);
	std::sort(a + 1, a + n + 1);
	for (int i(1); i <= n; ++ i) b[2 * i - 1] = a[i].a, b[2 * i] = a[i].b;
	std::sort(b + 1, b + 2 * n + 1);
	for (int i(1); i <= n; ++ i) {
		A[i] = std::lower_bound(b + 1, b + 2 * n + 1, a[i].a) - b;
		B[i] = std::lower_bound(b + 1, b + 2 * n + 1, a[i].b) - b;
	}
	make_tree(1, 1, n << 1);
	for (int i(1); i <= n; ++ i)
		if (A[i] <= B[i]) update(1, A[i], A[i], query(1, B[i] + 1, 2 * n) - query(1, A[i], A[i]) + 1);
		else {
			update(1, A[i], A[i], query(1, A[i], n << 1) - query(1, A[i], A[i]));
			update(1, B[i] + 1, A[i], 1);
		}
	printf("%d", query(1, 1, n << 1));
	return 0;
}