Moovie Mooving（状压DP）

题目：

n部电影，有时长和若干放映起始时间。Bessie可以在某部电影的放映阶段去看这部电影或中途离开。他不会看同一部电影2次。问Bessie最少需要看几部电影使得他在0~L时间段内一直看电影。(n最大20)

做法：

状压DP。 表示在状态下Bessie能连续看电影到的最远时间。是二进制状态。第i位为1表示第i部电影已经看过，0表示没看过。转移的时候就找一个中的一个0将它置1。表示下一部要看的电影就是它。然后在这部电影的放映时间vector中二分第一个比当前时间小的放映时间。用+电影时长更新就好了。
转移：
统计最少的电影数量：

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 21;
const int inf = 0x3f3f3f3f;
int movie_time[N], dp[1<<N];
vector<int> movie_begin[N];
int get(int id, int x){
    int p = upper_bound(movie_begin[id].begin(), movie_begin[id].end(), x) - movie_begin[id].begin();
    if (p == 0) return 0;
    return movie_begin[id][p-1]+movie_time[id];
}
int cntbit(int sta){
    int cnt = 0;
    for (int i = sta; i >= 1; i -= i&(-i)) cnt++;
    return cnt;
}
int main(void){ 
    IOS;
    int n, L; cin >> n >> L;
    for (int i = 1; i <= n; ++i){
        cin >> movie_time[i];
        int m; cin >> m;
        for (int j = 1; j <= m; ++j){
            int x; cin >> x;
            movie_begin[i].push_back(x);
        }
    }
    for (int i = 1; i <= n; ++i){
        if (movie_begin[i][0] == 0) dp[1<<(i-1)] = movie_time[i];
    }
    int ans = inf;
    for (int i = 1; i < (1<<n); ++i){
        if (dp[i] >= L) ans = min(ans, cntbit(i));
        for (int j = 0; j < n; ++j){
            if (((i>>j)&1) == 0){
                dp[i|(1<<j)] = max(dp[i|(1<<j)], get(j+1, dp[i]));
            }
        }
    }
    if (ans == inf) ans = -1;
    cout << ans << endl;
    return 0;
}