[Luogu P3118] [USACO15JAN] Moovie Mooving

Luogu P3118

思路

状压DP

设$f_S$为选择集合$S$后最多可以看$0\dots f_S$的电影,转移的时候直接枚举$S$中$0$的位置,二分查找并转移

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

struct Data{
    int l, r;
    bool operator <(const Data &_)const{
        return l==_.l ? r<_.r : l<_.l;
    }
}a;

int N, L, cnt, f[1<<20], num[1<<20];

std::vector<Data>vec[25];
std::vector<Data>::iterator it;

int count(int _){
    int ans=0;
    while(_){
    	ans++; _-=_&(-_);
    }
    return ans;
}

int solve(int l, int qwq){
    a.l=l, a.r=0x3f3f3f3f;
    it=std::upper_bound(vec[qwq].begin(), vec[qwq].end(), a);
    if(it==vec[qwq].begin()) return -1;
    it--; 
    return it-vec[qwq].begin();
}

int main(){
    int D, M, ans=100;
    scanf("%d%d", &N, &L);
    for(int i=1; i<=N; i++){
        scanf("%d%d", &D, &M);
        for(int j=1; j<=M; j++){
            scanf("%d", &a.l);
            a.r=a.l+D;
            vec[i].push_back(a);
        }
    }
    for(int i=1; i<=N; i++) std::sort(vec[i].begin(), vec[i].end());
    for(int i=0; i<N; i++) num[1<<i]=i;
    for(int i=0; i<(1<<N); i++){
        int j=((1<<N)-1)^i;
        for(; j; j-=j&(-j)){
            int o=num[j&(-j)];
            int p=solve(f[i], o+1);
            if(p!=-1) 
                f[i|(1<<o)]=std::max(f[i|(1<<o)], vec[o+1][p].r);
        }
    }
    for(int j=0; j<(1<<N); j++) if(f[j]>=L)
        ans=std::min(ans, count(j));
    printf("%d\n", ans==100 ? -1 : ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注