POJ.1065 Wooden Sticks

1.Problem
http://poj.org/problem?id=1065

2.Idea
According to Dilworth Theorem, minimum number of ordered subtest is equal to the length of longest non-decreasing subsequence.

3.Source

 struct WoodenStick {  
      int l, w;  
      bool operator < (const WoodenStick &a)const {  
           if (l == a.l) return w < a.w;  
           else return l < a.l;  
      }  
 } WoodenSticks[5005];  
 int n;  
 int dp[5005];  
 int solve(int n)  
 {  
      memset(dp, -1, sizeof dp);  
      sort(WoodenSticks, WoodenSticks + n);  
      for (int i = 0; i < n; i++) {  
           *lower_bound(dp, dp + n, WoodenSticks[i].w, greater<int>()) = WoodenSticks[i].w;  
      }  
      return lower_bound(dp, dp + n, -1, greater<int>()) - dp;  
 }  
 int main()  
 {  
      int t;  
      cin >> t;  
      while (t--) {  
           cin >> n;  
           for (int i = 0; i < n; i++) {  
                scanf("%d%d", &WoodenSticks[i].l, &WoodenSticks[i].w);  
           }  
           cout << solve(n) << endl;  
      }  
 }