洛谷P3118: Moovie Mooving G
看到数据范围考虑状压,题目要求看的电影最少那就维护时间最大,我们设 \(f_{i}\) 为 \(i\) 状态最多可以看多久的电影,对于不在集合的点我们枚举转移。
我们每个开始时间都对应一个截至时间,问能加入这个点,每个点花费时间是固定的,我们又要不间断所以我们找到第一个不大于 \(f_{i}\) 的数作为起始时间,然后加上花费时间判断时间是否超过 \(L\)。
可以手动模拟一下,反正我是看懂了用二分找到能续上的电影。
#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1
#define re register
#define ll long long
const int N=5e5+10;
const int mod=998244353;
using namespace std;
int n,l;
int a[2000][2000];
int d[N];
int f[1<<20];
int ans=1e9;
int get(int x){
int sum=0;
while(x){
if(x&1){
sum++;
}
x>>=1;
}
return sum;
}
signed main(){
// freopen("kingdom3.in","r",stdin);
// freopen("a.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>l;
for(int i=0;i<n;i++){
cin>>d[i]>>a[i][0];
for(int j=1;j<=a[i][0];j++){
cin>>a[i][j];
}
}
memset(f,-1,sizeof f);
int full=(1<<n)-1;
f[0]=0;
for(int i=0;i<=full;i++){
if(f[i]==-1){
continue;
}
for(int j=0;j<n;j++){
int k=(1<<j);
if(i&k){
continue;
}
int pos=upper_bound(a[j]+1,a[j]+1+a[j][0],f[i])-a[j];
if(pos>1){
f[i|k]=max(f[i|k],a[j][pos-1]+d[j]);
}
else{
f[i|k]=f[i];
}
}
if(f[i]>=l){
ans=min(ans,get(i));
}
}
if(ans>=1e9){
cout<<-1;
return 0;
}
cout<<ans;
return 0;
}
标签:洛谷,int,题解,Moovie,P3118,ans,Mooving
From: https://www.cnblogs.com/sadlin/p/18541616