NC24158. [USACO 2015 Jan G]Moovie Mooving
描述
输入描述
The first line of input contains N and L.
The next N lines each describe a movie. They begin with its integer
duration, D (1 <= D <= L) and the number of showtimes, C (1 <= C <=
1000). The remaining C integers on the same line are each in the
range 0..L, and give the starting time of one of the showings of the
movie. Showtimes are distinct, in the range 0..L, and given in
increasing order.
输出描述
A single integer indicating the minimum number of movies that Bessie
needs to see to achieve her goal. If this is impossible output -1
instead.
示例1
输入:
4 100 50 3 15 30 55 40 2 0 65 30 2 20 90 20 1 0
输出:
3
C++14(g++5.4) 解法, 执行用时: 604ms, 内存消耗: 4732K, 提交时间: 2020-05-11 13:15:10
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
const int maxn = 21;
int dp[1<<maxn],len[maxn];
std::vector<int> ve[maxn];
int main(){
int n,L,m,t;
scanf("%d %d",&n,&L);
for(int i = 1;i <= n; ++i){
scanf("%d %d",len+i,&m);
while(m--){
scanf("%d",&t);
ve[i].push_back(t);
}
}
for(int i = 1;i < (1<<n); ++i){
for(int j = 1;j <= n; ++j){
if(i&(1<<(j-1))){
int p = upper_bound(all(ve[j]),dp[i^(1<<(j-1))])-ve[j].begin()-1;
if(p >= 0) dp[i] = max(dp[i],len[j]+ve[j][p]);
}
}
}
int ans = n+n;
for(int i = 0;i < (1<<n); ++i){
if(dp[i] >= L) ans = min(ans,__builtin_popcount(i));
}
printf("%d\n",(ans<=n?ans:-1));
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 633ms, 内存消耗: 4728K, 提交时间: 2020-05-14 14:04:12
#include<bits/stdc++.h>
using namespace std;
int DP[1100005],a[25],b[25][1005];
int main()
{
int i,j,k,t,n,l,ans=30;
scanf("%d%d",&n,&l);
for(i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i][0]);
for(j=1;j<=b[i][0];j++)scanf("%d",&b[i][j]);
}
for(i=1;i<1<<n;i++)
{
for(j=0;j<n;j++)
{
if((1<<j)&i)
{
k=i^(1<<j);
t=upper_bound(b[j+1]+1,b[j+1]+1+b[j+1][0],DP[k])-b[j+1]-1;
if(t)DP[i]=max(DP[i],b[j+1][t]+a[j+1]);
}
}
if(DP[i]>=l)ans=min(ans,__builtin_popcount(i));
}
if(ans==30)ans=-1;
printf("%d\n",ans);
return 0;
}