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; }轉載于:https://www.cnblogs.com/forever97/p/bzoj1852.html
總結
以上是生活随笔為你收集整理的BZOJ 1852 [MexicoOI06]最长不下降序列（贪心+DP+线段树+离散化）的全部內容，希望文章能夠幫你解決所遇到的問題。
