【每日一题】Moovie Mooving 状压dp

题意：n部电影 每部电影有m个放映机会和放映时间 希望在0~l的这段时间内不停的看电影 允许看到一半出来 但不允许跳出来再跳回去 求满足条件下看的电影部数最少

思路：
n只有20大 考虑搜索或者状压dp 但每部电影还有不同放映时间 且范围来到1000 就只能是状压dp 用dp[i] 来表示i表示二进制集合下看电影时间最久
状态转移为

#include <bits/stdc++.h>

using namespace std;

const int N = 21;

vector<int> v[N];
int dp[1 << N];
int a[N];

int cal(int x){
    int sum = 0;

    while(x){
        if(x&1){
            sum ++ ;
        }
        x >>= 1;
    }
    return sum;
}

int main(){
    int n, l ;

    cin >> n >> l ;

    for(int i = 0;i < n;i ++){
        cin >> a[i];
        int m ;cin >> m ;

        for(int j = 0;j < m;j ++){
            int x;cin >> x;
            v[i].push_back(x);
        }
    }

    int res = 30;

    for(int i = 1;i <= 1 << n;i ++){
        for(int j = 0;j < n;j ++){
            if(i & (1 << j)){
                int k = i ^ (1 << j);
                int pos = upper_bound(v[j].begin(),v[j].end(),dp[k]) - v[j].begin() - 1;

                if(pos >= 0){
                    dp[i] = max(dp[i],v[j][pos] + a[j]);
                }
            }
        }
        if(dp[i] >= l){
            res = min(res,cal(i));
        }
    }

    if(res == 30){
        res = -1;
    }

    cout << res << '\n';

    return 0;
}