题意
有n个电影可以看,现在有一段持续时间为0到L,让这段时间内一直观看电影不存在空闲时间,每个电影有个持续播放的时间和电影的场次,以及每场的开始时间。
一部电影只能进入观看一次,电影可以中途进入观看或者中途退出。问从0到L之间一直观看电影,最少要看几部电影。

思路
N只有20,容易想到状压
图片说明
转移的话,枚举i的每个二进制位,从剩余状态转移过来即可。
如果dp[i]为time,那么意味着从1~i之间我们都是可以持续观看的,所以转移时候,我们找到当前要转移到的这个电影的一个开始场次≤time的位置,这里以为输入的电影场次的开始时间是单调的,可以通过二分得到。(注意一下这里的二分我们要的是≤的最后一个,可以直接upper找到>的第一个,下标在减去1,就是≤的最后一个了)
并且对于电影,肯定是看完,才能保证dp[i]最大
所以容易得到dp[sta]=max(dp[sta],c[i][pos]+a[i])

#include<bits/stdc++.h>
using namespace std;
int dp[1<<21];
int a[25],c[25][1005];
int cal(int x){
    int num=0;
    while(x) num+=x&1,x>>=1;
    return num;
}
int main(){
    int n,l;cin>>n>>l;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>c[i][0];
        for(int j=1;j<=c[i][0];j++){
            cin>>c[i][j];
        }
    }
    int ans=25;
    for(int sta=1;sta<1<<n;sta++){
        for(int i=0;i<n;i++){
            if(sta>>i&1){
                int k=sta^(1<<i);
                int pos=upper_bound(c[i+1]+1,c[i+1]+c[i+1][0]+1,dp[k])-c[i+1];
                pos--;
                if(pos>=1) dp[sta]=max(dp[sta],c[i+1][pos]+a[i+1]);
            }
        }
        if(dp[sta]>=l) ans=min(ans,cal(sta));
    }
    if(ans==25) cout<<-1;
    else cout<<ans;
    return 0;
}