bzoj5185 [Usaco2018 Jan]Lifeguards

bzoj5185 [Usaco2018 Jan]Lifeguards

​​ Description 农夫约翰为他的奶牛们开了一个游泳池，他认为这将有助于他们放松和生产更多的牛奶。为确保安全，他请了N只 牛做救生员，每只牛都有一个工作时间，为一些连续的时间间隔为了简单起见，泳池每天从时间0打开到到10^9， 所以每个区间都可以用两个整数来描述，给定的这两个整数就是区间的开始和结束时刻。例如，一个救生员从t = 4时开始工作和在t=7时结束，共覆盖三个时间单位（注意端点也是覆盖到的时间点）。但不幸的是，农夫约翰雇佣 了比它支付能力多出K个的救生员。他需要开除正好K个救生员，求出剩余的救生员最大能够覆盖多长的时间（一段 时间被覆盖当且仅当这时有至少一个救生员在工作） Input 第一行包含N和K（K≤N≤10^5，1≤K≤100） 接下来的N行，每行描述一个在区间1…10^9上的救生员 给定这个救生员区间的开始和结束位置，其中有些救生员的区间可能会相交。 Output 请输出一个数字，表示如果农夫约翰开除K个救生员，剩余救生员最大能够覆盖的时间长度 Sample Input 3 2 1 8 7 15 2 14 Sample Output 12 农夫约翰应该开除掉覆盖1…8和7…15两个区间的两个救生员 HINT Source Platinum 鸣谢WenDavid提供翻译 首先贪心的把包含于其他线段的线段删除 然后按照左端点排序 那么显然右端点也是单调递增的 设dp[i][k]表示 前i条线段删除k条 i这条线段必须选的最大覆盖长度是多少 那么dp[i][k]=max{dp[j][k-(i-j-1)]}; 那么显然可以知道我加入由dp[x][y]->dp[i][j] 那么显然我需要满足 x-y=i-j-1 那么如果i与j 不相交的时候 我可以储存我这个dp的最大值 然后直接加上len[i]即可 如果相交的话 我可以设dp[i][j]+line[i].r-line[x].l所以我针对我后面这个维护多个单调队列即可 然后最后统计答案的时候相当于 我枚举我最后一条边选取的是哪些边 这样的话恰好保证答案的不重不漏

#include#include#include#include#define pa pair#define N 100010#define fi first#define se secondusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x*f;}int dp[N][110],mx[N],n,k;deque q[N];struct node{ int l,r;}init[N],line[N];inline bool cmp(const node &a,const node &b){ return a.l==b.l?a.rmxr) line[++cnt]=init[i],mxr=init[i].r;else --k; }if (k<0) k=0;n=cnt; for (int i=1;i<=n;++i){ for (int j=0;j<=k;++j){if (j>=i) break;int lt=i-j-1; while(!q[lt].empty()&&line[q[lt].front().fi].r=q[lt].back().se) q[lt].pop_back(); q[lt].push_back(make_pair(i,tmp)); } }int ans=0; for (int i=1;i<=n;++i) if (k>=(n-i)) ans=max(ans,dp[i][k-(n-i)]);printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。