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
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] 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;
}