題目說(shuō)了很多，其實(shí)就是一個(gè)最長(zhǎng)上升子序列的問(wèn)題，傳統(tǒng)的n^2算法在這里會(huì)超時(shí)，所以改用二分的算法，1000MS的時(shí)限用掉110MS,差強(qiáng)人意，但不知還有沒(méi)有更快的算法，希望各位大牛能指點(diǎn)一二。
代碼如下：（閱讀前建議先閱讀我轉(zhuǎn)的上一篇關(guān)于算法介紹的文章）
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 40000;
int a[N], C[N], f[N]; // f[i]用于記錄a[0
i]的最大長(zhǎng)度
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;
}