# POJ 1065 Wooden Sticks ( Dilworth theorem, LIS )

1065 -- Wooden Sticks

Dilworth Theorem

T 筆測資。給 N 個座標，求排序後最少的相鄰對數滿足右邊的點不在以左邊的點為原點的第一象限 ( 在線上也算第一象限 )。

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n , 1 <= n <= 5000 , that represents the number of wooden sticks in the test case, and the second line contains 2n positive integers l1 , w1 , l2 , w2 ,..., ln , wn , each of magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.

O( N lg N ) / O( N )

```#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

signed main(){
ios::sync_with_stdio( 0 );
int T; cin >> T;
for( int ti = 0; ti < T; ++ti ){
int N; cin >> N;
vector< pair< int, int > > P( N );
for( int i = 0; i < N; ++i ){
cin >> P[ i ].first >> P[ i ].second;
}
sort( P.begin(), P.end() );
vector< int > lis( N, 1 << 30 );
for( int i = 0; i < N; ){
int j = i;
while( j < N and P[ j ].first == P[ i ].first ){
int x = lower_bound( lis.begin(), lis.end(), - P[ j ].second ) - lis.begin();
lis[ x ] = - P[ j ].second;
++j;
}
i = j;
}
cout << lower_bound( lis.begin(), lis.end(), 1 << 30 ) - lis.begin() << endl;
}
return 0;
}
```