Moovie Mooving

题意:给n个电影,一个时长L,然后问在时长L中最少看多少个电影,没个只能看一次,中间可以跳场
题解:状态压缩dp,看了好多大佬写的,(刚看会)
枚举所有的观看的组合的可能,然后讲i转化为二进制,比如 ,第一,五,六场不看,第二,三,四场看
然后我们对于每一种组合的情况进行处理
对于第i种情况下的第j个电影我们放在最后进行观看,那么我们要在前面求出不看第j个电影的一个时间,设为 因为可以中间退出,所以求小于等于的最大第j个电影的开始时间的数,然后再加上第j个电影的播放时间
然后对于每个如果大于L 求其中二进制的1的个数,即为答案
时间复杂度:

#include<cstdio>
#include<algorithm>
using namespace std;
int f[1050000],t[21],d[21],a[21][1001],num[1050000];
int search(int p,int x)
{
    int l=1,r=d[p],mid,ans=-1;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(a[p][mid]<=x)
        ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
int main()
{
    int n,m,i,j,k,ans=30;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&t[i],&d[i]);
        for(j=1;j<=d[i];j++)
        scanf("%d",&a[i][j]);
    }
    for(i=1;i<1<<n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(i&(1<<(j-1)))
            {
                k=search(j,f[i^(1<<(j-1))]);
                if(k!=-1)
                f[i]=max(f[i],a[j][k]+t[j]);
            }
        } num[i]=num[i-(i&(-i))]+1;
        if(f[i]>=m)
        ans=min(ans,num[i]);
    }

    printf("%d\n",ans==30?-1:ans);
    return 0;
}