Moovie Mooving 题解

一.闲话

英文题真难受，盯google盯了好久qwq，输入部分还是看样例解释看出来的qwq,英语菜鸡没人权qwq

二.题解

这道题，题意是：

有n场电影，每场电影都有若干场。

给你每个电影的播放时间以及每场的开始时间，问你，要连续不断的看电影直到看到l为止，最少需要看几部电影（每部电影最多看一场）

明显的dp/贪心题目，仔细分析后，发现并不能贪心，所以考虑dp

注意到，l很大，所以直接dp的话是不行的，但是，n很小（n<=20）,于是我们从这里入手，n<=20的话，那么一般考虑搜索或者状压dp(复杂度正好合适)，首先，搜索的话，我们只能枚举看哪些电影，至于看哪场，就又需要考虑了，所以暂不考虑搜索。

然后，就是状压dp了。

我们明显可以设dp[i]表示现在状态为i,我们最多可以看到多久。

如果我们要从状态x转移到其他状态，肯定就是枚举当前看哪部电影。

那么，我们方程怎么办？

我们对每一部我们枚举的电影，我们找到开始时间小于等于dp[x]的最大的那个（也即是我们当前能看的这部电影中，最晚结束的那部），因为这样才能把转移过去的dp变得最大，而，直接枚举哪场肯定布星，我们发现，题目中说了，开始时间是递增的（不是递增我们排个序就好2333），于是，找到"最晚的符合条件的开始时间"是可以通过二分来实现的。

最后，我们算完之后，枚举每个状态，看哪些状态的dp值大于等于l，再在这些状态中找1的个数最少的那个即可~

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=(1<<20),M=21;
int dp[N];
int D[M],C[M],T[M][1001];
int main(){
    int n,l;
    scanf("%d%d",&n,&l);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&D[i],&C[i]);
        for(int j=1;j<=C[i];++j){
            scanf("%d",&T[i][j]);
        }
    }
    int tot=(1<<n)-1;
    for(int i=0;i<tot;++i){
        for(int j=1;j<=n;++j){
            if((i>>(j-1))&1)continue;
            int v=(i|(1<<(j-1)));
            dp[v]=max(dp[v],dp[i]);
            int l=1,r=C[j],res=0;
            while(l<=r){
                int mid=(l+r)>>1;
                if(T[j][mid]>dp[i]){
                    r=mid-1;
                }else if(T[j][mid]+D[j]<=dp[i]){
                    l=mid+1;
                }else{
                    res=mid,l=mid+1;
                }
            }
            if(res){
                dp[v]=max(dp[v],T[j][res]+D[j]);
            }
        }
    }
    int ans=2e9;
    for(int i=0;i<=tot;++i){
        if(dp[i]>=l){
            int res=0;
            for(int j=1;j<=n;++j){
                res+=((i>>(j-1))&1);
            }
            ans=min(ans,res);
        }
    }
    if(ans==2e9){//无解
        puts("-1");
        return 0;
    }
    printf("%d",ans);
    return 0;
}