在看完谷歌翻译后 本英语菜鸡大概弄懂了这题的题意 n部电影 每部电影有多个不同放映时间 同一部电影只看一次
看完 n和l 的范围 这一看就是状压dp 但dp方程表达什么??
这里我表达的是 最长放映时长
我们用二进制枚举选了哪几部电影 放映时间选择最近的小于放映时长的(使用二分寻找)
这样就出来了 代码有详细注释
#include <bits/stdc++.h> #define ll long long using namespace std; int a[25],n,l,dp[1<<22],f[25][1100]; int cal(int x){ int num=0; while(x) num+=x&1,x>>=1; return num; } int main() { cin>>n>>l; for(int i=1;i<=n;++i) { cin>>a[i]>>f[i][0]; for(int j=1;j<=f[i][0];++j) cin>>f[i][j]; } int ans=25; for(int i=1;i<(1<<n);++i){ for(int j=0;j<n;++j){ if(i>>j&1){///这部电影被选了 int k=i^(1<<j);///没有选当前这部电影的dp值(当前时长 int pos=upper_bound(f[j+1]+1,f[j+1]+1+f[j+1][0],dp[k])-f[j+1];///第一个大于等于这个dp值的放映时间的下标 pos--;///选出第一个小于此dp值的下标 (下一部电影的放映时间要小于等于当前时长 if(pos) dp[i]=max(dp[i],f[j+1][pos]+a[j+1]);///放映时间+放映时长 } if(dp[i]>=l) ans=min(ans,cal(i));///有几个1(总时长达到要求 } } if(ans==25)cout<<-1<<endl; else cout<<ans<<endl; return 0; }