• 如果喜欢本站,您可以按CTRL+D收藏本站,方便下次访问。

  • 欢迎来自五湖四海的朋友,期待为您分享有价值的资源 :oops:

POJ 1631-Bridging signals 最长上升子序列

POJ解题 第四度 10年前 (2010-08-13) 30次浏览 0个评论 扫描二维码

file

//Bridging signals 1631 最长上升子序列 dp问题 2010.8.13
#include<iostream>
using namespace std;
const int MAXP=40005;
int L[MAXP];
int bSearch(int left,int right,int num)
{
    if(right==left)

        return left;

    int mid=(left+right)/2;

    if(num==L[mid])

        return mid;

    else    if(num>L[mid])

    {

        if(right<mid+1)

            return mid;

        else 

            return bSearch(mid+1,right,num);

    }

    else if(num<L[mid])     {         if(left>mid-1)

            return mid;

        else

            return bSearch(left,mid,num);

    }

    else return mid;

}

int solve(int n)

{

    int ans=0;

    int temp=0;

    int count=0;

    scanf("%d",&temp);

    L[ans++]=temp;

    n--;

    while(n--)

    {

        scanf("%d",&temp);

        if(temp>L[ans-1])

            L[ans++]=temp;

        else

            L[bSearch(0,ans-1,temp)]=temp;

    }

    return ans;

}

int main()

{

    int t,n;

    cin>>t;

    while(t--)

    {

        cin>>n;

        cout<<solve(n)<<endl;
    }
    return 0;
}

本网站采用BY-NC-SA 4.0协议进行授权 | 转载请注明原文链接:https://www.disidu.com/post/1006.html
如果觉得本文对您有帮助或者您心情好~可以微信打赏支持一下本站:↓↓↓
喜欢 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址