POJ1631 LIS模板

两种nlogn的方法。

1.树状数组优化暴力。有种扫描线的感觉，以时间保证位置，把值作为数组脚标。

2.记录长为...的上升子序列末尾元素最小值；如果新入元素a比d [ top ]大，就d [ ++top ] = a，否则二分查找第一个d的值大于a的地方，用a更新该d。答案为top。

　　二分的边界之类的需注意。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int t,n,a,d,f[],ans;

int query(int k)

{

    int ret=;

    while(k)

    {

        ret=max(ret,f[k]);

        k-=k&-k;

    }

    return ret;

}

void add(int k)

{

    while(k<=n)

    {

        f[k]=max(f[k],d);

        k+=k&-k;

    }

}

int main()

{

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i=;i<=n;i++)

        {

            scanf("%d",&a);

            d=query(a)+;

            ans=max(ans,d);

            add(a);

        }

        printf("%d\n",ans);

        ans=;

        memset(f,,sizeof f);

    }

    return ;

}

树状数组

#include<iostream>

#include<cstdio>

using namespace std;

int t,n,a,d[],l,r,ret,top;

int main()

{

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i=;i<=n;i++)

        {

            scanf("%d",&a);

            if(a>d[top])

            {

                d[++top]=a;continue;

            }

            l=;r=top;ret=-;

            while(l<r)////////

            {

                int mid=(l+r)/;

                if(d[mid]>a)ret=mid,r=mid;

                else l=mid+;

            }

            if(d[l]>a)ret=l;///////

            d[ret]=a;

        }

        printf("%d\n",top);

        top=;

    }

    return ;

}

二分

巴特西

POJ1631 LIS模板

最新文章

热门文章