洛谷P1020 导弹拦截(偏序问题，求最长不上升子列和最长上升子列的nlogn算法)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1541

此前有一道更简单的二维偏序问题：hdu1541(Stars)

分析：同样是偏序问题，使用树状数组可以降低复杂度到nlogn

代码1：n^2的dp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n=0,h[maxn],dp[maxn],fp[maxn];
int main()
{
    while(~scanf("%d",&h[++n]));
    n--;
    /*
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);
    */
    for(int i=1;i<=n;i++) dp[i]=fp[i]=1;
    for(int i=1;i<n;i++)
        for(int j=n;j>=1+i;j--)
        {
            if(h[j]<=h[i]) dp[j]=max(dp[j],dp[i]+1);
            else fp[j]=max(fp[j],fp[i]+1);
        }
    int ans1=0,ans2=0;
    for(int i=1;i<=n;i++) 
    {
        ans1=max(ans1,dp[i]);
        ans2=max(ans2,fp[i]);
    }
    printf("%d\n%d",ans1,ans2);
    return 0;
}

代码2：上树状数组

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 2;
const int range = 50002;
int c[range],h[maxn];
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int y)
{
    while(x<=range)
    {
        c[x]=max(c[x],y);   x+=lowbit(x);
    }
}
int query(int x)
{
    int ans=0;
    while(x)
    {
        an***ax(ans,c[x]);  x-=lowbit(x);
    }
    return ans;
}
int main()
{
    int a=0,b=0,n=0;
    while(scanf("%d",&h[++n])!=EOF);
    n--;
	memset(c,0,sizeof(c));
    for(int i=n;i>=1;i--)
    {
        int x=query(h[i])+1;
        add(h[i],x);
        a=max(a,x);
    }
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++)
    {
        int x=query(h[i]-1)+1;
        add(h[i],x);
        b=max(b,x);
    }
    printf("%d\n%d",a,b);
    return 0;
}