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