Moovie Mooving G

设 \(f[i][S]\) 表示在第 \(i\) 场（注意是场，不是部）电影时，已经看了 \(S\) 里面的电影是否合法。

然后贪心地取 \(|S|\) 最小的状态保存。光荣 MLE 了， \(21\%\)。

发现当一场电影结束后，无论这一场是在哪里看的都没关系。

因此我们设 \(f[S]\) 表示只看集合 \(S\) 里面的电影，最多能够看多久。

转移就枚举下一场看什么，二分一下小于等于 \(f[S]\) 的第一场比赛并观看即可。

复杂度 \(O(n2^n\log C)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=20;
int n,m,res=INF,x,y;
int f[1<<N],len[N];
vector<int> v[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d%d",&len[i],&x);
        while(x--){
			scanf("%d",&y);
			v[i].push_back(y);
		}
    }
    for(int x=0;x<(1<<n);x++){
        if(f[x]>=m){
			res=min(res,__builtin_popcount(x));
			continue;
		}
        for(int i=0;i<n;i++){
            if(x&(1<<i)) continue;
            vector<int>::iterator it=upper_bound(v[i].begin(),v[i].end(),f[x]);
            if(it==v[i].begin()) continue;
            it--;
            f[x|(1<<i)]=max(f[x|(1<<i)],*it+len[i]);
        }
    }
    printf("%d\n",res==INF?-1:res);
    return 0;
}