题意

奶牛要在电影院待够 分钟。
有 个电影，第 个电影时长为 ，有 个放映时间，分别为 。
每个电影只能看一次，奶牛可以在任何播放时间内进入和退出该电影。问奶牛能待够 分钟所需要看的最少电影数。
数据范围：。

分析

注意到 ，而且电影观看顺序有影响，所以必须记录状态。
一开始的想法是设 表示看的电影集合为 ，时间为 的状态能否到达，这样电影数就是 （ 中 的个数）。
不过这样显然时间和空间是爆炸的！！
然后发现其实不用记录哪些时间能到达，因为假设时间 能到达，时间 也一定能到达（因为可以中途退出），于是只用记录能到达的最长时间即可。
于是令 表示看的电影集合为 所能到达的最长时间。
那么怎么转移呢？
我们枚举最后看的电影为 ，记 为 除掉 后的集合，那么找到小于等于 的最大 来更新 即可，这个可以通过二分解决。
觉得还是比较难以说明啊！！具体还是结合代码理解，代码比较好懂且有比较详细的注释！！
还有代码看起来复杂度是 的，其实是 ，具体原因可以考虑二分的次数，其实只有 次。

代码如下

#include <bits/stdc++.h>
#define N 20
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
vector<int> d[N];
int a[N];
int f[1 << N];
int count(int x){
    int s = 0;
    while(x){
        s++;
        x -= x&-x;
    }
    return s;
}
int main(){
    int i, j, t, k, n, m, L, ans = 21;
    n = read(); L = read();
    for(i = 0; i < n; i++){
        a[i] = read(); m = read();
        while(m--) d[i].push_back(read());
        d[i].push_back(1e8 + 1);//为了 upper_bound 有解 
    }
    for(i = 0; i < (1 << n); i++){//枚举电影集合 
        for(j = 0; j < n; j++){//枚举 i 中的 j 
            if(1 << j & i){
                t = i ^ (1 << j); 
                k = upper_bound(d[j].begin(), d[j].end(), f[t]) - d[j].begin() - 1;//找到小于等于 f[t] 的最大 d[j][k] 
                if(k >= 0 && d[j][k] + a[j] > f[t]) f[i] = max(f[i], d[j][k] + a[j]);//更新 f[i] 
            }
        }
        if(f[i] >= L) ans = min(ans, count(i));//如果可行，更新答案，即为 i 中 1 的个数 
    }
    if(ans != 21) printf("%d", ans);
    else printf("-1");
    return 0;
}