CSUST-2018区域赛选拔个人赛-1019 看直播（二分+DP）

题意：n个区间，要选出一些不相交（端点也不能相交）的区间，求最长的长度

n <= 2e5

思路：跟某个经典的贪心模型很像不过却是个DP。

题解的线段树优化DP听他们说我也不知道什么鬼，然后今天写了个二分出来的

早知道不写模拟题多好。。我就不适合当模拟题选手。。。

代码看起来很短是lowerbound的功劳

先把区间按右端点（结束时间）排序，设dp[i]为前i个区间的答案，然后用类似n^2的LIS的方法去转移，这里因为已经按右端点排好序了就可以二分了，我直接重载了一个lowerbound的cmp来判断两个区间不相交

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #define LL long long
 6 #define debug(x) cout << "[" << x << "]" << endl
 7 using namespace std;
 8 
 9 const int mx = 2e5+10;
10 int dp[mx];
11 
12 struct seg{
13     int l, r;
14     bool operator < (const seg& a) const{
15         return r < a.r;
16     }
17 }a[mx];
18 
19 bool cmp(seg a, seg b){
20     return a.r < b.l;
21 }
22 
23 int main(){
24     int n;
25     scanf("%d", &n);
26     for (int i = 1; i <= n; i++)
27         scanf("%d%d", &a[i].l, &a[i].r);
28     sort(a+1, a+n+1);
29     for (int i = 1; i <= n; i++)
30         dp[i] = a[i].r-a[i].l+1;
31     for (int i = 2; i <= n; i++){
32         int sum = dp[i];
33         int k = lower_bound(a+1, a+i+1, a[i], cmp)-a;
34         if (k >= 1) sum += dp[k-1];
35         dp[i] = max(dp[i-1], sum);
36     }
37     printf("%d
", dp[n]);
38     return 0;
39 }

upd：看了队里一个神仙的线段树代码

对不起打扰了看不懂啊

https://paste.ubuntu.com/p/FmBbkKtTXP/