洛谷P5464 缩小社交圈 题解
题目链接：P5464 缩小社交圈
题意：
社交圈子里有 $n$ 个人，每个人都有一个 SAN 值范围 $[l_i,r_i]$。当两个人的 SAN 值交集不为空时，这两个人有 PY 关系。
现在希望从社交圈子里面挑选出一些人组成一个集合 $S$，如果将所有集合内的人中有 PY 关系的那一对人都连上边，则 $S$ 刚好成为一个树（森林不行哦）。
请问，有多少种可以选择的方案？由于答案可能很大，请对 $10^{9}+7$ 取模。
输入格式：
第一行一个整数 $n$。
接下来 $n$ 行，每行 2 个整数，表示这个人的 SAN 值区间。
输出格式：
一行一个整数，表示答案。
数据范围：
满足 $n \leq 2000,1 \leq l_{i} <r_{i} \leq 4000 $ 。
首先把所有线段按右端点升序排序，这样我们可以依次考虑每条线段。
注意到答案的树形如一条长链，其中一些节点挂了几个单点。
考虑设 $f(i,j)$ 表示编号最右侧的线段是 $i$ ，次右的是 $j$ 时的合法方案数。
记 $S(i,j) = \sum_{1 \le j < i} f(i,j)$ ，答案就是 $n + \sum S(i,i-1)$ 。
并记 $\operatorname{pre}(i)$ 为比 $i$ 编号小的线段中编号最大的不与 $i$ 相交的线段的编号。
转移暴力枚举 $i$ 左侧的线段 $j~(1 \le j < i)$ ，除了 $r_j < l_i$ 的线段外（不相交），
- 若 $l_j < l_i$ ，$j$ 可能和左侧的点连上，则
- 否则 $i$ 可能和左侧的点连上，有
最后更新一下 $S(i,j)=S(i,j-1) + f(i,j)$ ，这实际上是前缀和优化。
时间复杂度 $\mathcal{O}(n^2)$
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
template<typename T> void add(T &x, T y = 0) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e3 + 15))
struct node{ int l, r; } a[N];
int n, pre[N], sum[N][N], dp[N][N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n; rep(i, 1, n) cin >> a[i].l >> a[i].r;
sort(a + 1, a + 1 + n, [](node x, node y) { return x.r < y.r; });
rep(i, 1, n) Rep(j, i - 1, 1)
if(a[j].r < a[i].l) { pre[i] = j; break; }
rep(i, 1, n) rep(j, 1, i - 1)
{
if(a[j].r < a[i].l) { sum[i][j] = sum[i][j - 1]; continue; }
if(a[i].l > a[j].l) { add(dp[i][j] = sum[j][pre[i]], 1ll); }
else { add(dp[i][j] = sum[i][pre[j]], 1ll); }
add(sum[i][j] = dp[i][j], sum[i][j - 1]);
}
int res = n % mod;
rep(i, 1, n) add(res, sum[i][i - 1]);
cout << res << '\n';
return 0;
}参考文献：
