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;
}