[USACO 2015 Gold] Moovie Mooving

作法：

明顯是位元DP。對於一個電影的集合，求出從0開始看完這些電影所花的最大時間為何，那麼因為他可以中途離場，這也就代表所有 <= 最大時間的時間點都可以是「剛看完這些電影的時間」，轉移的時候就挑最晚的可以看的電影轉移就可以了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=20+1 ;
 
vector<int> v[maxn] ;
int t[maxn],dp[1<<maxn] ;
main()
{
    if(fopen("movie.in","r"))
    {
        freopen("movie.in","r",stdin) ;
        freopen("movie.out","w",stdout) ;
    }
 
    int n,L ; scanf("%d%d",&n,&L) ;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&t[i]) ;
        int k ; scanf("%d",&k) ;
        while(k--)
        {
            int x ; scanf("%d",&x) ;
            v[i].push_back(x) ;
        }
    }
 
    int ans=n+1 ;
    for(int i=1;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++) if(i&(1<<j))
        {
            int id=upper_bound(v[j].begin(),v[j].end(),dp[i^(1<<j)])
                    -v[j].begin()-1 ;
            if(id>=0) dp[i]=max(dp[i],max(dp[i^(1<<j)],v[j][id]+t[j])) ;
        }
        if(dp[i]>=L) ans=min(ans,__builtin_popcount(i)) ;
    }
    printf("%d\n",ans==n+1?-1:ans) ;
}