随笔-38  评论-23  文章-0  trackbacks-0

简单的概括下 这题的意思就是求一个最长上升子序列.由于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 米游 阅读(311) 评论(0)  编辑 收藏 引用 所属分类: ACM

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