程序员人生 网站导航

【BZOJ3886】【Usaco2015 Jan】Moovie Mooving 状态压缩 动态规划

栏目:php教程时间:2015-03-16 11:14:14

广告:

#include <stdio.h> int main() { puts("转载请注明出处[vmurder]谢谢"); puts("网址:blog.csdn.net/vmurder/article/details/44040735"); }

题意:

PoPoQQQ要在电影院里呆L分钟,这段时间他要看小型电影度过。电影1共N部,每部都播放于若干段可能堆叠的区间,PoPoQQQ决不会看同1部电影两次。现在问他要看最少几部电影才能度过这段时间?
注:必须看电影才能在电影院里呆着,同时1场电影可以在其播放区间内任意时间入场出场。

题解:

状压DP,f[i]表示状态为i时从0最远连续看到哪。
然后转移上枚举还要看哪部电影,贪心取能看的片场中最靠后的1个。
然后时间复杂度O(2N×N×xxxx)
其中xxxx是求能看片场中最靠后1个的时间复杂度。

求法1:

2分。xxxx=log2C

求法2:

类似单调队列预处理1发,然后xxxx=1

代码:

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 22 #define M 1010 #define inf 0x3f3f3f3f using namespace std; int n,m,S,f[1<<N],ans=inf; int len[N],p[N],c[N][M]; int find(int x,int id) { int l=-1,r=p[id]-1,mid,ans; while(l<r) { int mid=l+r+1>>1; if(c[id][mid]<=x)l=mid; else r=mid-1; } return l; } int main() { freopen("test.in","r",stdin); int i,j,k; scanf("%d%d",&n,&m),S=1<<n; for(i=0;i<n;i++) { scanf("%d%d",&len[i],&p[i]); for(j=0;j<p[i];j++)scanf("%d",&c[i][j]); } memset(f,-1,sizeof f),f[0]=0; for(i=0;i<S;i++) { if(f[i]==-1)continue; if(f[i]>=m) { for(j=0,k=i;k;k-=(k&-k))j++; ans=min(ans,j); continue; } for(j=0;j<n;j++) { if(i&(1<<j))continue; k=find(f[i],j); if(k==-1)continue; f[i|(1<<j)]=max(f[i|(1<<j)],c[j][k]+len[j]); } } printf("%d ",ans==inf?-1:ans); return 0; }
------分隔线----------------------------
------分隔线----------------------------

最新技术推荐