posts - 218, comments - 61, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

LIS模板

Posted on 2008-08-23 01:02 魔のkyo 阅读(399) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

前段时间发现自己的求解最优值的LIS模板有错(虽然过了ZJU和PKU的题目,以及在若干contest中用其过题都没有发生问题),而后修正了,今天发现就连自己的求解最优解的LIS模板都有错,真是汗。。。
这里是测试的地方,只挂掉第6,10组数据就算过了。
http://www.rqnoj.cn/Problem_Show.asp?PID=167

下面两个模板,求解最优值的是我自己写的,求解最优解的是我收的,用STL写的比较精简

int* binary(int* b,int* e,int x)
{
    
int *mid;
    
if(x<*b)return b;
    
while(b<e-2){
        mid
=b+(e-b)/2;
        
if(*mid<x) b=mid;//此处修改严格或非严格 
        else e=mid+1;
    }
    
return e-1;
}
 
int LIS(int a[],int n)
{
    
if(!n)return 0;
    
int i,k;
    
int *b=new int[n];
    b[
0]=a[0];
    k
=1;
    
for(i=1;i<n;++i){
        
if(b[k-1]<a[i]) b[k++]=a[i];//此处修改严格或非严格 
        else *binary(b,b+k,a[i])=a[i];
    }
    delete [] b;
    
return k;
}

/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
template
<typename T> vector<int> LIS(vector<T> &a)
{
    vector
<int> b, p(a.size());
    
int u, v;
    
if (a.size() < 1return b;
    b.push_back(
0);
    
for (int i = 1; i < (int)a.size(); i++) {
        
if (a[b.back()] < a[i]) {
            p[i] 
= b.back();
            b.push_back(i);
            
continue;
        }
        
for (u = 0, v = b.size()-1; u < v;) {
            
int c = (u + v) / 2;
            
if (a[b[c]] < a[i]) u=c+1else v=c;
        }
        
if (a[i] < a[b[u]]) {
            
if (u > 0) p[i] = b[u-1];
            b[u] 
= i;
        }
    }
    
for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
    
return b;
}
只有注册用户登录后才能发表评论。