poj 1631 Bridging signals 最长上升子序列

//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 argc, char *argv[])
{
    
int t,n;
    cin
>>t;
    
while(t--)
    
{
        cin
>>n;
        cout
<<solve(n)<<endl;
    }

    
    
return 0;
}


posted on 2010-08-13 15:09 若余 阅读(197) 评论(0)  编辑 收藏 引用


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


导航

<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

统计

常用链接

留言簿

随笔档案(16)

搜索

最新随笔

最新评论

评论排行榜