【转】最长上升子序列的NlogN方法（单调队列）

2009-12-10 08:54

#include <fstream>
using namespace std;
ifstream fin("a.in");
ofstream fout("a.out");
const int maxN = 10000, oo = 2000000000;
int N , ans = 0, data[maxN], Len[maxN];

int find(int lo , int hi , int val)//在单调队列里二分查找

{
    if( lo + 1 == hi) return lo ;
    int mid = lo + (hi - lo)/2;
    if(Len[mid] == val) return -1;
    if( Len[mid] < val) return find( mid , hi ,val);
    return find(lo , mid , val);
}

void dp()
{
     for( int i = 2; i <= maxN ; i++) Len[i] = oo ;
     Len[0] = -1 ; Len[1] = data[1] ;
     for( int i = 2 ; i <= N ; i++)
     {
          int index = find(0 , i, data[i]);
          if(index == -1) continue;
          Len[index + 1] <?= data[i] ;
          ans >?= index + 1;
     }
}

int main()
{
    fin>>N;
    for( int i = 1; i <= N; i++) fin>>data[i];
    dp();
    fout<<ans<<endl;
    return 0 ;
}