【CJOJ68】Open

题目描述

地主lightdog有\(N\)个狗腿子,他们严守着他们的基地。 基地只有一扇门,基地里面可以自由地开关门,但是基地外面的人需要一把钥匙才能开关门。

\(N\)个狗腿子每个都有任务要执行。第\(i\)个狗腿子需要在第\(l_i\)时刻离开基地,在第\(r_i\)时刻回来。 其余时间不允许接近基地的门。保证对任意\(i,j\),有\(l_i\ne r_j\);对任意\(i\ne j\),有\(l_i\ne l_j,r_i\ne r_j\)。 在时刻\(l_i\)一个狗腿子出门后,门会变成开的,如果他有钥匙那么他可以决定是否关门;否则他无法关门。 在时刻\(r_i\)一个狗腿子到达时,不允许出现这样的情况:门是关的且他没有钥匙。

但是,lightdog只有\(K\)把钥匙,只能分给\(K\)个狗腿子。为了基地的安全,他需要求出门处于开的状态的最短时间。 对题意不清楚的可以参照样例解释。

输入格式

输入文件的第一行是两个正整数\(N,K\)

接下来\(N\)行,每行两个正整数\(l_i,r_i\)

输出格式

输出一个正整数表示门处于开的状态的最短时间。

数据范围

本题采用捆绑测试。

对于第一个subtask,\(N\le 20\),分值\(30\)分;

对于第二个subtask,\(N\le 200\),分值\(30\)分;

对于第三个subtask,\(N\le 2000\),分值\(40\)分。

对于所有数据,\(1\le l_i<r_i\le 10^9\)

题解

显然这道题是农64黑我的

于是我得A掉这个题

首先分析,若拿钥匙的人已经确定,那么哪些时间开门,哪些时间关门

将不拿钥匙的人出门标记为(,回来标记为),拿钥匙的出入都标记为|(因为都可以开或者关,效果相同)

那么判断按时间线排序后每两个时间点之间的开关情况

(开|,(开),(开(,

|关(,|关|,|开),

)关(,)关|,)开)

找一下规律:形如(*或者*)的是要开的

从逻辑角度分析,就是没钥匙的出门之后关不上门要开着,没钥匙的回来之前门要开着

然后就可以DP了

但是会发现没法计算每一个狗腿子拿了钥匙对答案的贡献

因为有可能出现这样的情况:(),其中两个括号分属两个不同狗腿子

那么仅一个狗腿子拿到钥匙后并不能使中间部分变成关

于是想了个比较鬼的方法。。

先将每个狗腿子重新排序,使每个()其中两个括号分属两个不同狗腿子的两个狗腿子中占据右括号的在占据左括号的前一个

dp[i][j][k]表示前i个狗腿子,用j把钥匙,最后一个狗腿子有没有用钥匙的关闭时间最大值

然后就可以转移了==

说点什么

您将是第一位评论人!

提醒
wpDiscuz