0w1

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.

解法:
其實就是要一個最少集合划分數,滿足每個集合的任意兩點都滿足其中一個點在另一個點的右上方。考慮 Dilworith 定理。這裡令「一個點在另一個點的右上方」為比較函數,又根據結論「最少鏈划分數等於最長反鏈長度」,和最長反鏈為含最多點的一條負斜率直線,可以求得解。對 x 升序排序,一樣則 y 升序排序後,可以轉換為 LIS 問題。

時間 / 空間複雜度:
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;
}