Description
农夫约翰为他的奶牛们开了一个游泳池,他认为这将有助于他们放松和生产更多的牛奶。为确保安全,他请了N只
牛做救生员,每只牛都有一个工作时间,为一些连续的时间间隔为了简单起见,泳池每天从时间0打开到到10^9,
所以每个区间都可以用两个整数来描述,给定的这两个整数就是区间的开始和结束时刻。例如,一个救生员从t =
4时开始工作和在t=7时结束,共覆盖三个时间单位(注意端点也是覆盖到的时间点)。但不幸的是,农夫约翰雇佣
了比它支付能力多出K个的救生员。他需要开除正好K个救生员,求出剩余的救生员最大能够覆盖多长的时间(一段
时间被覆盖当且仅当这时有至少一个救生员在工作)
Input
第一行包含N和K(K≤N≤10^5,1≤K≤100)
接下来的N行,每行描述一个在区间1…10^9上的救生员
给定这个救生员区间的开始和结束位置,其中有些救生员的区间可能会相交。
Output
 请输出一个数字,表示如果农夫约翰开除K个救生员,剩余救生员最大能够覆盖的时间长度
Sample Input
3 2
1 8
7 15
2 14
Sample Output
12
农夫约翰应该开除掉覆盖1…8和7…15两个区间的两个救生员
HINT
Source

首先贪心的把包含于其他线段的线段删除 然后按照左端点排序 那么显然右端点也是单调递增的
设dp[i][k]表示 前i条线段删除k条 i这条线段必须选的最大覆盖长度是多少
那么dp[i][k]=max{dp[j][k-(i-j-1)]};
那么显然可以知道我加入由dp[x][y]->dp[i][j] 那么显然我需要满足 x-y=i-j-1
那么如果i与j 不相交的时候 我可以储存我这个dp的最大值 然后直接加上len[i]即可 如果相交的话 我可以设dp[i][j]+line[i].r-line[x].l所以我针对我后面这个维护多个单调队列即可
然后最后统计答案的时候相当于 我枚举我最后一条边选取的是哪些边 这样的话恰好保证答案的不重不漏

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论