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;
}
时间: 04-23

BZOJ 2225 [Spoj 2371]Another Longest Increasing(CDQ分治)的相关文章

SPOJ LIS2 Another Longest Increasing Subsequence Problem 三维偏序最长链 CDQ分治

Another Longest Increasing Subsequence Problem Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19929 Description Given a sequence of N pairs of integers, find the length of the longest incre

SPOJ - LIS2 Another Longest Increasing Subsequence Problem

cdq分治,dp(i)表示以i为结尾的最长LIS,那么dp的递推是依赖于左边的. 因此在分治的时候需要利用左边的子问题来递推右边. (345ms? 区间树TLE /********************************************************* * ------------------ * * author AbyssFish * **********************************************************/ #inclu

中南OJ1551: Longest Increasing Subsequence Again(分块+离散化线段树)

1551: Longest Increasing Subsequence Again Time Limit: 2 Sec  Memory Limit: 256 MB Submit: 29  Solved: 15 [Submit][Status][Web Board] Description Give you a numeric sequence. If you can demolish arbitrary amount of numbers, what is the length of the

300. Longest Increasing Subsequence

Problem statement: Given an unsorted array of integers, find the length of longest increasing subsequence. For example,Given [10, 9, 2, 5, 3, 7, 101, 18],The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there

[email&#160;protected] [329] Longest Increasing Path in a Matrix (DFS + 记忆化搜索)

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/ Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally o

Dynamic Programming | Set 3 (Longest Increasing Subsequence)

在 Dynamic Programming | Set 1 (Overlapping Subproblems Property) 和 Dynamic Programming | Set 2 (Optimal Substructure Property) 中我们已经讨论了重叠子问题和最优子结构性质,现在我们来看一个可以使用动态规划来解决的问题:最长上升子序列(Longest Increasing Subsequence(LIS)). 最长上升子序列问题,致力于在一个给定的序列中找到一个最长的子序列

[LeetCode]Longest Increasing Path in a Matrix

题目:Longest Increasing Path in a Matrix Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the bounda

Longest Increasing Common Subsequence (LICS)

最长上升公共子序列(Longest Increasing Common Subsequence,LICS)也是经典DP问题,是LCS与LIS的混合. Problem 求数列 a[1..n], b[1..m]的LICS的长度, a[], b[]数组的元素均为正整数. Solution 考虑如何定义DP状态,定义DP状态就是定义所谓的最优子问题(optimal subproblem),而DP状态要能转移,就是所谓最优子问题要具有重叠子结构. 将DP状态定义为 DP[i][j]:a[1..i], b[

spoj 1811 LCS - Longest Common Substring (后缀自动机)

spoj 1811 LCS - Longest Common Substring 题意: 给出两个串S, T, 求最长公共子串. 限制: |S|, |T| <= 1e5 思路: dp O(n^2) 铁定超时 后缀数组 O(nlog(n)) 在spoj上没试过,感觉也会被卡掉 后缀自动机 O(n) 我们考虑用SAM读入字符串B; 令当前状态为s,同时最大匹配长度为len; 我们读入字符x.如果s有标号为x的边,那么s=trans(s,x),len = len+1; 否则我们找到s的第一个祖先a,它