【每日一题】5月11日 Moovie Mooving

题目大意：给定 部电影,影片放映时间 ,对应 次影片放映的开始时间.求在 时间内可以连续观看电影的最少数量.(一部电影放映时可以切换另一部正在放映的电影)

分析:状压dp

• 小于等于20，可以枚举所有选电影的方案. 表示 状态下连续放电影的结束时间.
• 考虑 的转移, 方案没有选的电影就是二进制位下为0的位置 ,因为 的放映时间是
  所以我们只要找到第 部电影放映时间在 之前即可.因为暴力枚举会TLE,而且给出放映时间的是单调递增,所以我们二分找即可.
• 答案就是所有符合 状态的下标 的二进制下 个数最小值.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn=1<<21;

int dp[maxn];
int d[22],c[22],b[22][1005];

int main()
{
    int n,l;
    cin>>n>>l;
    for( int i=1;i<=n;i++ )
    {
        cin>>d[i]>>c[i];
        for( int j=1;j<=c[i];j++ ) cin>>b[i][j];
    }
    int ans=1e9;
    for( int i=0;i<1<<n;i++ )
    {
        for( int j=1;j<=n;j++ )
        {
            if( i>>(j-1) & 1 ) continue;
            int k=(i|(1<<(j-1)));
            int idx=upper_bound(b[j]+1,b[j]+1+c[j],dp[i])-b[j];
            idx--;
            if( idx>0 ) dp[k]=max(dp[k],b[j][idx]+d[j]);
        }
        if( dp[i]>=l ) 
        {
            int res=__builtin_popcount(i);
            ans=min(ans,res);
        }
    }


    if( ans==(int)1e9 ) puts("-1");
    else printf("%d\n",ans); 
}