codeforces-#661-F

codeforces-#661-F

九月 03, 2020

F. Yet Another Segments Subset

题意

给出n<3000个区间[Li,Ri]分布在[1,2e5]的数轴上

问选出一种最大的区间集合(区间最多) 使得集合中的区间两两要么没有交集

要么其中一个是另一个的子集

题解

由于区间数很少而区间的左右端点在[1,2e5]上分布

所以首先需要离散化将左右端点根据排序后的大小映射到[1,6000]上

用区间dp统计答案 设计dp(L,R) 表示离散化后的坐标轴上

在[L,R]区间上(不一定为输入区间)能选出最大的符合条件的区间集合

根据区间dp的经验

首先枚举区间长度 在枚举区间左端点 枚举区间中间点mid

得到dp转移的伪代码

1
2
3
4
5
6
for Len < Maxlen:
	for L < Maxlen-len:
		R=L+len-1;
		for L < mid < R:
			if([L,R]是输入的区间)dp[L][R]=max(dp[L][R],dp[L][mid]+dp[mid+1][R]+1)
			else if([L,R]不是输入的区间)dp[L][R]=max(dp[L][R],dp[L][mid]+dp[mid+1][R])

但是这种dp时间复杂度为$On^3$

发现可以通过枚举具体的分割点而不是粗略的[L,R]中所有的点作为分割点

为此我们需要设置vector Rg[L]存入以L为区间左端点对应的所有右端点R

当用传统区间dp时枚举左端L时若输入的区间中存在一个区间的左端点=L

那么以Rg[L]为mid 作为分割点 那么有

1
2
3
if([L,R]是输入的区间)dp(L,R)=max(dp(L,R),dp(L,Rg[L])+dp(Rg[L]+1,R)+1 )

else if([L,R]不是输入的区间)dp(L,R)=max(dp(L,R),dp(L,Rg[L])+dp(Rg[L]+1,R) )

这种枚举方式虽然表面上三层for循环也是$n^3$复杂度

实际上在枚举区间左端的和分割点这两个for循环

相当于遍历了所有输入区间(n个区间)一次

所以内层两个循环实际上为$On$复杂度

所以总体复杂度为$On^2$ 

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
54
55
56
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=6e3+5;
const double Pi=acos(-1);
const ll mod=1e9+7;
/*
*/
struct Segments{
    int indx;
    int L,R;
}arr[Max];
int dp[Max][Max];
int main() {
    Turnoff;
	int t;cin>>t;
	while(t--){
        int n;cin>>n;
        vector<int>resort;
        for(int i=0;i<n;i++){
            cin>>arr[i].L>>arr[i].R;
            arr[i].indx=i;
            resort.push_back(arr[i].L);
            resort.push_back(arr[i].R);
            //arr[i].len=(arr[i].R-arr[i].L+1);
        }
        sort(resort.begin(),resort.end());
        resort.erase(unique(resort.begin(),resort.end()),resort.end());
        for(int i=0;i<n;i++){
            arr[i].L=lower_bound(resort.begin(),resort.end(),arr[i].L)-resort.begin();
            arr[i].R=lower_bound(resort.begin(),resort.end(),arr[i].R)-resort.begin();
            //arr[i].len=arr[i].R-arr[i].L+1;
        }
        vector<int>Rg[Max];int Maxlen=resort.size();
        for(int i=0;i<n;i++)Rg[arr[i].L].push_back(arr[i].R);
        ///memset(dp,0,sizeof dp);
        //for(int i=0;i<n;i++)sort(Rg[arr[i].L].begin(),Rg[arr[i].L].end());
        for(int i=0;i<Maxlen;i++)for(int j=0;j<Maxlen;j++)dp[i][j]=0;
        for(int i=0;i<Maxlen;i++)dp[i][i]=0;
        for(int len=1;len<=Maxlen;len++){
            for(int L=0;L+len-1<Maxlen;L++){
                int R=L+len-1;
                bool add=count(Rg[L].begin(),Rg[L].end(),R);
                //cout<<add<<endl;
                dp[L][R]=max(dp[L][R],dp[L+1][R]+add);
                for(auto rg:Rg[L]){
                    if(rg>=R)continue;
                    dp[L][R]=max(dp[L][R],add+dp[L][rg]+dp[rg+1][R]);
                }
            }
        }
        cout<<dp[0][Maxlen-1]<<endl;
	}
}