题解 P3118 【[USACO15JAN]Moovie Mooving G】

题目链接

Solution [USACO15JAN]Moovie Mooving G

题目大意：有(n leq 20)种电影，每种有个片长，以及不同的放映开始时间集合(t)，(|t|leq1000)。求在每种电影只能观看一次的情况下能否从时刻(0-L)持续不断地观看电影

状压dp

---

分析：首先对于一个电影集合(S)，我们不关心内部究竟是如何安排时间表的，我们只贪心地将能持续不断观看电影的结束时间给推迟

于是我们可以使用状压dp

记(f[S])表示电影集合(S)最长能持续不断看多久，我们枚举(k otin S)，以第(k)种电影进行转移。

暴力的话一种电影最多有(1000)部，我们只需要找最后可行的一部，二分即可

最后在所有满足(f[S]geq L)中取(min{|S|})就是答案

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 23;
inline int read(){
	int x = 0;char c = getchar();
	while(!isdigit(c))c = getchar();
	while(isdigit(c))x = x * 10 + c - '0',c = getchar();
	return x;
}
int n,L,len[maxn],f[1 << maxn],ans = 114514;
vector<int> vec[maxn];
inline int cnt(int x){
	int res = 0;
	for(int i = 0;i < n;i++)
		if((x >> i) & 1)res++;
	return res;
}
int main(){
	n = read(),L = read();
	for(int i = 0;i < n;i++){
		len[i] = read();
		int x = read();
		while(x--)vec[i].push_back(read());
	}
	for(int now = 0;now < (1 << n);now++)
		for(int k = 0;k < n;k++)
			if(((now >> k) & 1) == 0){
				int pos = upper_bound(vec[k].begin(),vec[k].end(),f[now]) - vec[k].begin() - 1;
				if(pos == -1)continue;
				f[now | (1 << k)] = max(f[now | (1 << k)],max(f[now],vec[k][pos] + len[k]));
			}
	for(int now = 0;now < (1 << n);now++)
		if(f[now] >= L)ans = min(ans,cnt(now));
	printf("%d
",ans == 114514 ? -1 : ans);
	return 0;
}