题面翻译：

奶牛贝西想连续看L (1 <= L <= 100,000,000)分钟的电影，有 N (1 <= N <= 20)部电影可供选择，每部电影会在一天的不同时段放映。

贝西可以在一部电影播放过程中的任何时间进入或退出放映厅。但她不愿意重复看到一部电影，所以每部电影她最多看到一次。她也不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅。

请帮贝西计算她能够做到从0到L分钟连续不断地观看电影，如果能，请计算她最少看几部电影就行了。

好恶心的一道题！！！

这道题是让我们求最小观看电影个数，那么题意就可以简化成：

每个电影只能看一次，且为了保持观看电影个数最小，所以除了最后到l的一场，其他的都不能中途离开---->即她也不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅。

然后看数据范围：

一眼状压

现在，我们定为看了S集合里的电影最多可以看多少分钟。

集合中的说明看过，说明没有。

那么我们可以通过宽搜来枚举S的所有情况

用表示当前状态，表示当前讨论的点，表示目标状态——>

然后我们就可以通过二分查找找到最接近的第个电影的开场时间和电影的长度来更新

最后扫一遍所有的状态，找到看了分钟后的一种状态使最少

优化：

通过一个打表的思路，先算出每个的二进制下的的个数，最后遍历的时间复杂度为

注：

• 找到的第一个超过l就是正解了——因为宽搜保证看的电影数量递增
• 下列代码建议用手写二分，队列，读入优化

code:

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
queue<int> q;
const int N=22;
const int K=1005;
bool vis[1<<N];
const int inf=1e9;
//arr[i][j]:表示第i部电影的第j场的开始时间
int n,len,t[N],k[N],arr[N][K],f[1<<N],tot,cnt[1<<N],ans=inf;
int main(){
    scanf("%d %d",&n,&len);
    tot=(1<<n)-1;
    for(int i=1;i<=tot;i++){//初始化找1的个数 
        cnt[i]=cnt[i>>1];
        if(i&1)
            cnt[i]++;
    }
    for(int i=1;i<=n;i++){
        scanf("%d %d",&t[i],&k[i]);
        for(int j=1;j<=k[i];j++)
            scanf("%d",&arr[i][j]);
        if(!arr[i][1]){//初始化f数组
            int p=(1<<(i-1));
            f[p]=t[i];
            q.push(p);
            vis[p]=true;
        }
    }
    while(q.size()){
        int p=q.front();
        q.pop();
        vis[p]=false;//p状态标记为不在队列中 
        if(f[p]>=len)
            break;//第一个f[q]超过len分钟就是正解了 
        for(int i=1;i<=n;i++){
            if((p>>(i-1))&1)
                continue;
            int tt=p|(1<<(i-1));
            int l=upper_bound(arr[i]+1,arr[i]+1+k[i],f[p])-arr[i]-1;//找出最接近f[p]的开场时间来更新f[p]
            if(f[tt]<arr[i][l]+t[i] && f[tt]<len){
                f[tt]=arr[i][l]+t[i];
                if(!vis[tt]){
                    vis[tt]=true;//标记进队 
                    q.push(tt);
                }
            }
        }
    }
    for(int i=1;i<=tot;i++){
        if(f[i]<len)//已经超过时间的直接跳过 
            continue;
        ans=min(ans,cnt[i]);
    }
    if(ans<inf)
        printf("%d",ans);
    else
        puts("-1");
    return 0;
}