[文章目录]
Description
PoPoQQQ要在电影院里呆L分钟，这段时间他要看小型电影度过。电影一共N部，每部都播放于若干段可能重叠的区间<=1000 ，PoPoQQQ决不会看同一部电影两次。现在问他要看最少几部电影才能度过这段时间？ 注：必须看电影才能在电影院里呆着，同时一场电影可以在其播放区间内任意时间入场出场。n<=20
状压DP，dp[s]表示看完s状态的电影所能度过的最长时间，枚举下一个看的电影，二分转移即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,dp[1<<21],mp[30][1100],w[30],len[30],ans=inf;
int query(int x,int y)
{
int id=upper_bound(mp[x]+1,mp[x]+len[x]+1,y)-mp[x]-1;
if(id>=0) return mp[x][id]+w[x];
else return (int)(0xefefefef);
}
int work(int x)
{
int re=0;
while(x) {re++; x-=-x&x;}
return re;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d%d",w+i,len+i);
for(int j=1;j<=len[i];++j)
scanf("%d",mp[i]+j);
}
memset(dp,0xef,sizeof dp); dp[0]=0;
for(int s=0;s<(1<<n);++s)
{
for(int i=0;i<n;++i) if(!(s&(1<<i)))
dp[s|(1<<i)]=max(dp[s|(1<<i)],query(i+1,dp[s]));
if(dp[s]>=m) ans=min(ans,work(s));
}
if(ans==inf) puts("-1");
else printf("%d",ans);
return 0;
}