首页 > 代码库 > BZOJ 2225 [Spoj 2371]Another Longest Increasing（CDQ分治）
BZOJ 2225 [Spoj 2371]Another Longest Increasing（CDQ分治）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2225
【题目大意】
给定N个数对(xi,yi)，求最长上升子序列的长度。
上升序列定义为{(xi,yi)}满足对i<j有xi<xj且yi<yj。
【题解】
CDQ分治，将每个区间按照a排序，用区间左边的数据来更新右边的最长上升序列，
为排除a相等但是b上升情况的误统计，在排序时加入下标作为第二关键字，
使得a相等的情况下标小的后更新。
【代码】
#include <cstdio>#include <algorithm>using namespace std;const int N=100010;int n,a[N],b[N],c[N],d[N],dp[N],p[N],q[N];bool cmp(int x,int y){ if(a[x]==a[y])return x>y; return a[x]<a[y];}void CDQ(int l,int r){ if(l==r)return; int mid=(l+r)>>1; CDQ(l,mid); for(int i=l;i<=r;i++)q[i]=i; sort(q+l,q+r+1,cmp); for(int i=l;i<=r;i++){ if(q[i]<=mid)for(int j=b[q[i]];j<=p[0];j+=j&-j)c[j]=max(c[j],dp[q[i]]); else for(int j=b[q[i]]-1;j;j-=j&-j)dp[q[i]]=max(dp[q[i]],c[j]+1); }for(int i=l;i<=r;i++)if(q[i]<=mid)for(int j=b[q[i]];j<=p[0];j+=j&-j)c[j]=0; CDQ(mid+1,r);}int main(){ while(~scanf("%d",&n)){ p[0]=0; for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]),p[++p[0]]=b[i],dp[i]=1; sort(p+1,p+p[0]+1); p[0]=unique(p+1,p+p[0]+1)-p-1; for(int i=1;i<=n;i++)b[i]=lower_bound(p+1,p+p[0]+1,b[i])-p; CDQ(1,n); int ans=0; for(int i=1;i<=n;i++)ans=max(ans,dp[i]); printf("%d\n",ans); }return 0;}BZOJ 2225 [Spoj 2371]Another Longest Increasing（CDQ分治）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。