The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 1631 Bridging signals——最长上升子序列 DP(nlogn)

题目说了很多,其实就是一个最长上升子序列的问题,传统的n^2算法在这里会超时,所以改用二分的算法,1000MS的时限用掉110MS,差强人意,但不知还有没有更快的算法,希望各位大牛能指点一二。
代码如下:(阅读前建议先阅读我转的上一篇关于算法介绍的文章)
#include<iostream>
#include
<cstdio>
using namespace std;


const int N =  40000;

int a[N], C[N], f[N]; // f[i]用于记录a[0i]的最大长度

int bsearch(const int *C, int size, const int &a) 

{
    
    
int l=0, r=size-1;
    
    
while( l <= r ) 
        
    
{
        
        
int mid = (l+r)/2;
        
        
if( a > C[mid-1&& a <= C[mid] ) return mid; // >&&<= 换为: >= && <
        
        
else if( a < C[mid] ) r = mid-1;
        
        
else l = mid+1;
        
    }

    
}


int LIS(const int *a, const int &n){
    
    
int i, j, size = 1;
    
    C[
0= a[0]; f[0= 1;
    
    
for( i=1; i < n; ++i ){
        
        
if( a[i] <= C[0] ) j = 0;                 // <= 换为: <
        
        
else if( a[i] >C[size-1] ) j = size++;   // > 换为: >= 
        
        
else j = bsearch(C, size, a[i]);
        
        C[j] 
= a[i]; f[i] = j+1;
        
    }

    
    
return size;
    
}




int main()
{
    
int testcase;
    
int n;
    scanf(
"%d",&testcase);
    
int i,j;
    
for(i=1;i<=testcase;i++)
    
{
        scanf(
"%d",&n);
        
for(j=0;j<n;j++)
            scanf(
"%d",&a[j]);
        printf(
"%d\n",LIS(a,n));
    }

    
return 0;
}

posted on 2009-08-12 19:14 abilitytao 阅读(1846) 评论(1)  编辑 收藏 引用

评论

# re: POJ 1631 Bridging signals——最长上升子序列 DP(nlogn)[未登录] 2009-08-12 20:48 Bill Hsu

这题。。  回复  更多评论   


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