由于每个电影只能看一次,所以为了观看电影个数最小,所以除了最后一场电影之外,所以除了最后的一场,其他的都不能中途离开,去看别的电影。
由于数据时,所以很显然是左右的装压DP。我们可以设现在,我们定f[T]为看了T集合里的电影最多可以看多少分钟。对于每一个集合里,我们可以像其他装压DP题一样。用1的代表看过,用0代表没有看过。那么我们可以通过宽搜来枚举T的所有情况,用T表示当前状态,i表示当前讨论的点,t表示目标状态易证——>t=T|(1<<i)。然后我们就可以通过二分查找找到最接近f[T]的第i个电影的开场时间和电影i的长度来更新f[T]。最后暴力枚举所有的状态,找到看了T分钟后的一种状态使1最少。复杂度大约是,需要卡常才能过。
代码真的好长就不打了。。(其实是懒