【每日一题】Moovie Mooving

Translation(from 洛谷)

奶牛贝西想连续看L (1 <= L <= 100,000,000)分钟的电影，有 N (1 <= N <= 20)部电影可供选择，每部电影会在一天的不同时段放映。

贝西可以在一部电影播放过程中的任何时间进入或退出放映厅。但她不愿意重复看到一部电影，所以每部电影她最多看到一次。她也不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅。

请帮贝西计算她能够做到从0到L分钟连续不断地观看电影，如果能，请计算她最少看几部电影就行了。

Solution

看见 $N <= 20$ 的时候我就猜要用状压 $dp$ , 但是继续读题读不懂题意
果断跑去洛谷看翻译, 恍然大悟(英语菜鸡实锤慢着, 这题是紫题?)
考虑用二进制去枚举选择哪一部电影
令 $dp[i]$ 表示状态为 $i$ 的时候花费的最多连续时间
我们在枚举的时候可以二分查找 ( $upper\_bound$ ) 满足当前时间的最优电影时间
因为每部电影有他的放映时间, 我们要求最少的电影数
肯定是尽可能让时间往后使得错过放映时间
当连续时间大于 $l$ 的时候, 计算当前状态的二进制位上有多少个 $1$
更新答案, 取最优即可
注意不存在的时候要输出 $-1$ , 被坑了一下

Code

/*
  autor: Kurisu
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const long long inf = 1e14;
const int N = 1e6 + 5;
const double eps = 1e-10;
const ll mod = 1e9 + 7;

struct node {
  int p;
  int val[1005];
}a[25];
int dp[1 << 22];
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  int n, l;
  cin >> n >> l;
  for(int i = 0; i < n; i++) {
    cin >> a[i].p >> a[i].val[0];
    for(int j = 1; j <= a[i].val[0]; j++) {
      cin >> a[i].val[j];
    }
  }
  int ans = 1e9;
  memset(dp, -1, sizeof(dp));
  dp[0] = 0;
  for(int i = 0; i < (1LL << n); i++) {
    if(dp[i] == -1) continue; // 尚未到达/不存在的状态
    for(int j = 0; j < n; j++) {
      if(!(i & (1LL << j))) { // 没选过
        int pos = upper_bound(a[j].val + 1, a[j].val + a[j].val[0] + 1, dp[i]) - a[j].val;
        if(pos > 1) dp[i | (1LL << j)] = max(dp[i | (1LL << j)], a[j].val[pos - 1] + a[j].p); 
        else dp[i | (1LL << j)] = dp[i];
      }
    }
    if(dp[i] >= l) {
      ans = min(ans, __builtin_popcount(i));
    }
  }
  if(ans != 1e9)
    cout << ans << "\n";
  else cout << -1 << "\n";
  return 0;
}