poj 1631

這個題目是 給出一些連線關系，要你刪除一些連線使得剩下的連線最多並且 不相交。。

看到後面知道其實這個題目就是求最長上升子序列。。可以用dp做，不過要dp+二分，

我用的是樹狀數組來做，c來存前i個中的最長上升子序列，dat[i]=getmax(dat[i]-1)+1。。

[cpp] 
//============================================================================ 
// Name        : hello.cpp 
// Author      : lxw 
// Version     : 
// Copyright   : Your copyright notice 
// Description : Hello World in C++, Ansi-style 
//============================================================================ 
 
#include <iostream> 
using namespace std; 
 
#define MAXN 40010 
 
int dat[MAXN],c[MAXN];//c[i]表示前i個中的最長上升子序列 
int n; 
 
int lowbit(int x){return x&(-x);} 
 
void update(int i){ 
    int m=c[i]; 
    while(i<=n){ 
        if(c[i]<m)c[i]=m; 
        i+=lowbit(i); 
    } 
} 
 
int getMax(int i){ 
    int Max=0; 
    while(i>0){ 
        if(c[i]>Max)Max=c[i]; 
        i-=lowbit(i); 
    } 
    return Max; www.2cto.com
} 
 
int main() { 
    //setbuf(stdout,NULL); 
    int t; 
    scanf("%d",&t); 
    while(t--){ 
        scanf("%d",&n); 
        for(int i=1;i<=n;i++)scanf("%d",&dat[i]); 
        memset(c,0,sizeof(c)); 
        int maxnum=0; 
        for(int i=1;i<=n;i++){ 
            int tmp=c[dat[i]]=getMax(dat[i]-1)+1; 
            if(tmp>maxnum)maxnum=tmp; 
            update(dat[i]); 
        } 
        printf("%d\n",maxnum); 
    } 
    return 0; 
}