题面翻译：

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

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

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

好恶心的一道题！！！

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

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

然后看数据范围：

$n<=20$ 一眼状压

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

$S$ 集合中 $1$ 的说明看过， $0$ 说明没有。

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

用 $S$ 表示当前状态， $i$ 表示当前讨论的点， $s$ 表示目标状态——> $s=S|(1<<i)$

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

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

优化：

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

注：

$bfs$ 找到的第一个 $f[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;
}

Moovie Mooving

题面翻译：

好恶心的一道题！！！

然后看数据范围：

优化：

注：

code: