首页 > 代码库 > BZOJ 1852：[MexicoOI06]最长不下降序列（贪心+DP+线段树+离散化）
BZOJ 1852：[MexicoOI06]最长不下降序列（贪心+DP+线段树+离散化）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1852
【题目大意】
给你N对数A1,B1……An,Bn。要求你从中找出最多的对，
把它们按照一种方式排列，重新标号1,2,..,k。能满足对于每一对i<j,都有Ai>Bj。
【题解】
对于排序的问题，如果i必须要在j前面，
那么有A[i]>B[j],且B[i]>=A[j]，相加得A[i]+B[i]>A[j]+B[j]，
因此按A+B从大到小排序后最优，
我们先将A和B离散化，然后按照这个方式排序，
那么题目转化为，在偏序对<A,B>数列中选择最多个数对，使得对于i<j,都有Ai>Bj，
设dp[i][j]表示前i个数，A的最小值为j时的最优情况，
我们发现当Ai<=Bi时，dp[i][Ai]=max(dp[i][Bi+1……MAXNUM])+1
且对于别的dp答案没有贡献。
而当Ai>Bi的时候，dp[i][Ai]=max(dp[i][Ai……MAXNUM])+1
同时对于j属于[Ai+1,MAXNUM]的答案dp[i][j]=dp[i-1][j]+1
我们用线段树维护在固定时刻最小值为[1……MAXNUM]时的最优答案，
那么dp的转移就等价于线段树上的区间更新，单点更新和区间求极值。
按照顺序更新线段树，最后线段树上最大值即为答案。
【代码】
#include <cstdio>#include <algorithm>using namespace std; const int MAXN=2000000;struct node{int l,r,a,b,tag,max;}T[MAXN];int tot,n,m,l,r,c;void addtag(int x,int tag){ T[x].tag+=tag; T[x].max+=tag;}void pb(int x){ if(T[x].l){addtag(T[x].l,T[x].tag);addtag(T[x].r,T[x].tag);} T[x].tag=0;}void up(int x){T[x].max=max(T[T[x].l].max,T[T[x].r].max);}void build(int l,int r){ int x=++tot; T[x].a=l;T[x].b=r;T[x].tag=T[x].l=T[x].r=T[x].max=0; if(l==r)return; int mid=(l+r)>>1; T[x].l=tot+1;build(l,mid); T[x].r=tot+1;build(mid+1,r); up(x);}void change(int x,int a,int b,int p){ if(T[x].a>=a&&T[x].b<=b){addtag(x,p);return;} if(T[x].tag)pb(x); int mid=(T[x].a+T[x].b)>>1; if(mid>=a&&T[x].l)change(T[x].l,a,b,p); if(mid<b&&T[x].r)change(T[x].r,a,b,p);up(x);}int query(int x,int a,int b){ if(T[x].a>=a&&T[x].b<=b)return T[x].max; if(T[x].tag)pb(x);int mid=(T[x].a+T[x].b)>>1,res=0; if(mid>=a&&T[x].l)res=max(res,query(T[x].l,a,b)); if(mid<b&&T[x].r)res=max(res,query(T[x].r,a,b)); return res;}struct data{int a,b;}p[100010];bool cmp(data x,data y){return x.a+x.b>y.a+y.b;}int N,disc[200010];int remark(int x){ int l=1,r=2*N; while(l<=r){ int mid=(l+r)>>1; if(disc[mid]<x)l=mid+1; else if(disc[mid]==x)return mid; else r=mid-1; }}int main(){ while(~scanf("%d",&N)){ for(int i=1;i<=N;i++){ scanf("%d%d",&p[i].a,&p[i].b); disc[(i<<1)-1]=p[i].a; disc[i<<1]=p[i].b; }sort(disc+1,disc+(N<<1)+1); for(int i=1;i<=N;i++)p[i].a=remark(p[i].a),p[i].b=remark(p[i].b); sort(p+1,p+N+1,cmp); n=N<<1; build(1,n); for(int i=1;i<=N;i++){ if(p[i].a>p[i].b){ int t=query(1,p[i].a,n); int t1=query(1,p[i].a,p[i].a); change(1,p[i].a,p[i].a,t-t1); change(1,p[i].b+1,p[i].a,1); }else{ int t=query(1,p[i].b+1,n); int t1=query(1,p[i].a,p[i].a); change(1,p[i].a,p[i].a,t-t1+1); } }printf("%d\n",query(1,1,n)); }return 0;}BZOJ 1852：[MexicoOI06]最长不下降序列（贪心+DP+线段树+离散化）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。