每日一题：Moovie Mooving （状压dp）

题意

有 N 部电影，每部电影有不同的放映时常，和若干个放映起始时间。
Bessie 可以在一部电影播放过程中的任何时间进入或退出放映厅。每部电影她最多看1次且她不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅。

Bessie 能不能从0到L分钟连续不断地观看电影？如果能，计算她最少看几部电影。

$(1 \leq L \leq 100,000,000，1\leq N\leq 201≤L≤100,000,000，1≤N≤20)$

solution

$n$ 只有20考虑状压dp，$dp[i]$ 表示完成 $i$ 集合需要的最长时间，假设 $i$ 集合最后看的一部电影为 $j$，那么 $dp[i]$ 由 dp[i ^ (2^j)] 转移过来，并二分选取小于转移前集合的电影 $j$ 的最晚放映时间来更新 $p[i]$，同时维护 $dp[i] >=l $ 的最小集合为答案。时间复杂度 $O(2^n*log(1000))$

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 22;
int n, l, t[N], dp[1 << N];
vector<int> g[N];
int main() {
  cin >> n >> l;
  for (int i = 0; i < n; i++) {
    int c, x;
    cin >> t[i] >> c;
    while (c--) {
      cin >> x;
      g[i].push_back(x);
    }
    g[i].push_back(l);
  }
  int res = n + 1;
  for (int i = 1; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      if ((i >> j) & 1) {
        int now = i ^ (1 << j);
        int pos =
            upper_bound(g[j].begin(), g[j].end(), dp[now]) - g[j].begin() - 1;
        if (pos >= 0 && g[j][pos] + t[j] > dp[now])
          dp[i] = max(dp[i], g[j][pos] + t[j]);
      }
    }
    if (dp[i] >= l) res = min(res, __builtin_popcount(i));
  }
  if (res == n + 1)
    puts("-1");
  else
    cout << res << '\n';
  return 0;
}