Posted on 2008-08-23 01:02
魔のkyo 阅读(458)
评论(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() < 1) return 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+1; else 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;
}