洛谷P5464 缩小社交圈 题解
题目链接：P5464 缩小社交圈
题意：
社交圈子里有 \(n\) 个人，每个人都有一个 SAN 值范围 \([l_i,r_i]\)。当两个人的 SAN 值交集不为空时，这两个人有 PY 关系。
现在希望从社交圈子里面挑选出一些人组成一个集合 \(S\)，如果将所有集合内的人中有 PY 关系的那一对人都连上边，则 \(S\) 刚好成为一个树（森林不行哦）。
请问，有多少种可以选择的方案？由于答案可能很大，请对 \(10^{9}+7\) 取模。
输入格式：
第一行一个整数 \(n\)。
接下来 \(n\) 行，每行 2 个整数，表示这个人的 SAN 值区间。
输出格式：
一行一个整数，表示答案。
数据范围：
满足 $n ,1 l_{i} <r_{i} $ 。
首先把所有线段按右端点升序排序，这样我们可以依次考虑每条线段。
注意到答案的树形如一条长链，其中一些节点挂了几个单点。
考虑设 \(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\) 可能和左侧的点连上，则 \[ f(i,j) = S(j,\mathrm{pre}(i)) + 1 \]
否则 \(i\) 可能和左侧的点连上，有 \[ f(i,j) = S(i,\mathrm{pre}(j)) + 1 \]
最后更新一下 \(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;
}参考文献：
