链接
https://codeforces.com/contest/1399/problem/F
题意
$n$ 个区间，求最大区间集合，集合内的区间两两不相交或者一个包含于另一个中
思路
先离散化所有点
记 $dp[i][j]$ 为以 $i$ 为左端点，$j$ 为右端点的区间中合法的最大区间数
先考虑除本身外的子区间个数
情况一：不存在以 $i$ 为左端点的子区间
$dp[i][j]=max(dp[i][j],dp[i+1][j])(i<j)$
情况二：存在以 $i$ 为左端点的子区间
枚举所有以 $i$ 为左端点且右端点小于等于 $r$ 的区间：$dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j])(k<j)$
最后如果存在以 $i$ 为左端点，$j$ 为右端点的区间，$dp[i][j]+=1$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include<bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=6005;
int n,dp[N][N];
PII a[N];
VI b,v[N];
void pre() {
scanf("%d",&n);
b.clear();
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].FI,&a[i].SE),b.PB(a[i].FI),b.PB(a[i].SE);
sort(ALL(b));
b.resize(unique(ALL(b))-b.begin());
for(int i=1;i<=n;i++) {
a[i].FI=lower_bound(ALL(b),a[i].FI)-b.begin()+1;
a[i].SE=lower_bound(ALL(b),a[i].SE)-b.begin()+1;
}
for(int i=1;i<=SZ(b);i++) v[i].clear();
for(int i=1;i<=n;i++) v[a[i].FI].PB(a[i].SE);
for(int i=1;i<=SZ(b);i++)
for(int j=1;j<=SZ(b);j++)
dp[i][j]=-1;
}
int dfs(int l,int r) {
if(dp[l][r]!=-1) return dp[l][r];
dp[l][r]=0;
if(l>r) return 0;
bool cnt=count(ALL(v[l]),r);
dp[l][r]=max(dp[l][r],cnt+(l>=r?0:dfs(l+1,r)));
for(auto x:v[l]) dp[l][r]=max(dp[l][r],cnt+(x<r?dfs(l,x)+dfs(x+1,r):0));
return dp[l][r];
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
pre();
printf("%d\n",dfs(1,SZ(b)));
}
return 0;
}
|