题意:
有n个电影可以看,现在有一段持续时间为0到L,让这段时间内一直观看电影不存在空闲时间,每个电影有个持续播放的时间和电影的场次,以及每场的开始时间。
一部电影只能进入观看一次,电影可以中途进入观看或者中途退出。问从0到L之间一直观看电影,最少要看几部电影。
思路:
N只有20,容易想到状压
转移的话,枚举i的每个二进制位,从剩余状态转移过来即可。
如果dp[i]为time,那么意味着从1~i之间我们都是可以持续观看的,所以转移时候,我们找到当前要转移到的这个电影的一个开始场次≤time的位置,这里以为输入的电影场次的开始时间是单调的,可以通过二分得到。(注意一下这里的二分我们要的是≤的最后一个,可以直接upper找到>的第一个,下标在减去1,就是≤的最后一个了)
并且对于电影,肯定是看完,才能保证dp[i]最大
所以容易得到dp[sta]=max(dp[sta],c[i][pos]+a[i])
#include<bits/stdc++.h> using namespace std; int dp[1<<21]; int a[25],c[25][1005]; int cal(int x){ int num=0; while(x) num+=x&1,x>>=1; return num; } int main(){ int n,l;cin>>n>>l; for(int i=1;i<=n;i++){ cin>>a[i]>>c[i][0]; for(int j=1;j<=c[i][0];j++){ cin>>c[i][j]; } } int ans=25; for(int sta=1;sta<1<<n;sta++){ for(int i=0;i<n;i++){ if(sta>>i&1){ int k=sta^(1<<i); int pos=upper_bound(c[i+1]+1,c[i+1]+c[i+1][0]+1,dp[k])-c[i+1]; pos--; if(pos>=1) dp[sta]=max(dp[sta],c[i+1][pos]+a[i+1]); } } if(dp[sta]>=l) ans=min(ans,cal(sta)); } if(ans==25) cout<<-1; else cout<<ans; return 0; }