qoj8528 Chords 题解

数据随机有什么用？用你惊人的注意力可以观察到答案的值域在 \(800\) 附近。

考虑暴力 dp，设 \(dp_{l,r}\) 表示值域在 \([l,r]\) 中最多能选几个区间。假设 \(r\) 对应区间的左端点为 \(lst\)，那么有转移方程 \(dp_{l,r}=dp_{l,lst-1}+dp_{lst+1,r-1}+1\)。时间复杂度 \(O(n^2)\)。

因为答案很小，考虑交换 dp 答案和状态。设 \(dp_{r,i}\) 表示值域右端点在 \(r\)，答案为 \(i\) 时左端点最大值是多少。对于每一个 \(r\)，我们可以先二分求出 \([lst+1,r-1]\) 中最多可以选 \(x\) 个区间，那么有转移方程：\(dp_{r,i} = \max(dp_{r-1,i},dp_{lst-1,i-x-1})\)。时间复杂度 \(O(n \log V + nV)\)，实测 \(V\) 取 \(1000\) 能过。

//dzzfjldyqqwsxdhrdhcyxll
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f
const int MAXN = 1e5 + 10;
int n,l[MAXN],r[MAXN],lst[2 * MAXN],dp[2 * MAXN][1205];
signed main() {
	cin >> n;
	for(int i = 1;i <= n;i++) {
		cin >> l[i] >> r[i];
		lst[r[i]] = l[i];
	}
	memset(dp,-inf,sizeof dp);
	dp[0][0] = 0;
	for(int i = 1;i <= 2 * n;i++) {
		dp[i][0] = i;
		if(lst[i] == 0) {
			for(int j = 1;j <= 1200;j++) dp[i][j] = dp[i - 1][j];
		} else {
			for(int j = 1;j <= 1200;j++) dp[i][j] = dp[i - 1][j];
			int L = lst[i] + 1,R = i - 1;
			int ans = 0,ll = 0,rr = 1200;
			while(ll <= rr) {
				int mid = (ll + rr) >> 1;
				if(dp[R][mid] >= L) ans = mid,ll = mid + 1;
				else rr = mid - 1;
			}
			ans++;
			for(int j = 1;j <= 1200;j++) {
				if(ans >= j) dp[i][j] = max(dp[i][j],lst[i]);
				else dp[i][j] = max(dp[i][j],dp[lst[i]][j - ans]);
			}
		}
	}
	for(int i = 1200;i >= 0;i--) {
		if(dp[2 * n][i] >= 1) {
			cout << i;
			return 0;
		}
	}
	return 0;
}