另外发现以前好多人都栽在这俩点上了,而且我们的错误结果都一样。。。
/*
* File: main.cpp
* Author: Administrator
*
* Created on 2010年7月22日, 下午4:51
*/
/**/
#include <cstdlib>
#include <iostream>
#define min(a,b) a<b?a:b
using namespace std;
long lis(long,long);
long find(long);
long a[2002]={0};
long c[1001]={0};
long len=0;
int main(int argc, char** argv) {
long n=0;
cin >>n;
for(long i=1;i<=n;i++){
cin >>a[i];
a[i+n]=a[i];
}
long t=LONG_MAX;
for(long i=1;i<=n;i++)
t=min(lis(i,i+n-1),t);
cout <<t<<endl;
return 0;
}
long lis(long l1,long l2){
memset(c,0,sizeof c);
c[1]=a[l1];
len=1;
for(long i=l1+1;i<=l2;i++){
if(a[i]>=c[len]){c[++len]=a[i];continue;}
c[find(a[i])]=a[i];
}
return len;
}
long find(long x){
long i,j,mid;
i=1;j=len;
do{
mid=(i+j)>>1;
if(x==c[mid])return mid;
if(x<c[mid])j=mid-1;else i=mid+1;
}while(i<=j);
return i;
}
终于AC了,原来我一直写的nlgnLIS有问题,当初写拦截导弹时没注意,cheat过了,后来就忘了,这次终于找到这个bug了
下面分割线以内的就是修改内容
/*
* File: main.cpp
* Author: Administrator
*
* Created on 2010年7月22日, 下午4:51
*/
/**/
#include <cstdlib>
#include <iostream>
#define min(a,b) a<b?a:b
using namespace std;
long lis(long,long);
long find(long);
long a[2002]={0};
long c[1001]={0};
long len=0;
int main(int argc, char** argv) {
long n=0;
cin >>n;
for(long i=1;i<=n;i++){
cin >>a[i];
a[i+n]=a[i];
}
long t=LONG_MAX;
for(long i=1;i<=n;i++)
t=min(lis(i,i+n-1),t);
cout <<t<<endl;
return 0;
}
long lis(long l1,long l2){
memset(c,0,sizeof c);
c[1]=a[l1];
len=1;
for(long i=l1+1;i<=l2;i++){
if(a[i]>=c[len]){c[++len]=a[i];continue;}
c[find(a[i])]=a[i];
}
return len;
}
long find(long x){
long i,j,mid;
i=1;j=len;
do{
mid=(i+j)>>1;
--------------------------------------------------------------
if(x==c[mid]){
while(x==c[mid])mid++;
return mid;
}
--------------------------------------------------------------
if(x<c[mid])j=mid-1;else i=mid+1;
}while(i<=j);
return i;
}