随笔-38  评论-23  文章-0  trackbacks-0
pku 1631 DP(四)+二分查找

简单的概括下 这题的意思就是求一个最长上升子序列.由于number的数很多.用普通的n^2的DP求最长上升子序列肯定会超时。。故采用二分查找的方法。

#include<iostream>
using namespace std;
int num[40001],dp[40001],n;
int DP()
{
    int len=1,left,right,mid;
    dp[0]=num[0];
    for(int i=1;i<n;i++)
    {
        right=len-1,left=0;
        while(left<=right)
        {
            mid=(left+right)/2;
            if(num[i]<=dp[mid])
                right=mid-1;
            else
                left=mid+1;
        }
        dp[left]=num[i];
        if(left==len) len++;
    }
    cout<<len<<endl;
    return len;
}
int main()
{
    int T;
    cin>>T;
    while(T--&&cin>>n)
    {
        for(int i=0;i<n;i++)
            cin>>num[i];
        int len=DP();
    }
    return 0;
}
posted on 2009-04-01 13:14 米游 阅读(293) 评论(0)  编辑 收藏 引用 所属分类: ACM

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 米游