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.zzzyk.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;
}

作者：qingniaofy

补充：软件开发 , C++ ,