【题解】Moovie Mooving

题意：
有 N 部电影，每部电影有不同的放映时常，和若干个放映起始时间。
Bessie 可以在一部电影播放过程中的任何时间进入或退出放映厅。每部电影她最多看1次且她不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅。
Bessie 能不能从0到L分钟连续不断地观看电影？如果能，计算她最少看几部电影。
(1≤L≤100,000,000，1≤N≤20)

题解：
我们发现N很小，只有20，那就可以考虑状压，发现是电影时间是线性的可以通过转移来得到最长时间，那么可以通过状压DP来完成这道题了。

设dp[i]是状态i的时候能看到的最长时间是多少。

枚举每种状态和每种电影，对于如果要通过这部电影j转移，那么需要找到之前还没看这部电影的状态i^(1<<j)，然后新的这部电影j的起始时间≤dp[i^(1<<j)]，这个可以通过二分去查找，把这个电影起始时间下标记为pos。
那么转移方程为：

最后通过计算一下每个最长时间超过l的状态有多少个1，更新一下ans就行了。

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e3+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

int dp[1<<21];

int a[maxn];
int b[maxn][maxn];
int c[maxn];

int main(){
    int n,l;
    scanf("%d%d",&n,&l);
    for(int i=0;i<n;i++){
        scanf("%d",a+i);
        int m;scanf("%d",c+i);
        for(int j=0;j<c[i];j++){
            scanf("%d",&b[i][j]);
        }
    }
    int ans=inf;
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if((1<<j)&i){
                int tmp=i^(1<<j);
                int pos=upper_bound(b[j],b[j]+c[j],dp[tmp])-b[j]-1;
                if(pos>=0){
                    dp[i]=max(dp[i],dp[tmp]+a[j]);
                }
            }
        }
        int tmp=0;
        for(int j=0;j<30;j++){
            if(i&(1<<j)) tmp++;
        }
        if(dp[i]>=l) ans=min(ans,tmp);
    }
    printf("%d",ans);
    return 0;
}