NYOJ 16 矩形嵌套

題目描述：
有n個矩形，每個矩形可以用a,b來描述，表示長和寬。矩形X(a,b)可以嵌套在矩形Y(c,d)中當且僅當a<c,b<d或者b<c,a<d（相當於旋轉X90度）。例如（1,5）可以嵌套在（6,2）內，但不能嵌套在（3,4）中。你的任務是選出盡可能多的矩形排成一行，使得除最後一個外，每一個矩形都可以嵌套在下一個矩形內。
輸入
第一行是一個正正數N(0<N<10)，表示測試數據組數，
每組測試數據的第一行是一個正正數n，表示該組測試數據中含有矩形的個數(n<=1000)
隨後的n行，每行有兩個數a,b(0<a,b<100)，表示矩形的長和寬
輸出
每組測試數據都輸出一個數，表示最多符合條件的矩形數目，每組輸出占一行
樣例輸入
1
10
1 2
2 4
5 8
6 10
7 9
3 1
5 8
12 10
9 7
2 2
樣例輸出
5
解題思路：     1   DP最長的上升子序列
                       2   題目說了，矩形是可以旋轉90度的，那麼長和寬就是可以隨便的更改，根據貪心的思想，我們知道如果要得到最多的矩形嵌套，那麼長和寬的大小排序很重要，就是說盡量滿足矩形都能夠排成一個序列，這樣就能夠滿足最多的矩形嵌套，所以我麼輸入數據的時候，讓大的一個作為長，小的作為寬，那麼我們對長度進行排序，然後在從寬裡面查找最長的上升子序列即可

代碼：
[cpp] 
#include <algorithm> 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <vector> 
#include <cstdio> 
#include <stack> 
#include <queue> 
#include <set> 
using namespace std; 
#define MAXN 1010 
 
int t , n; 
int l[MAXN] , w[MAXN]; 
int dp[MAXN]; 
 
void solve(){ 
    int tmp_l[MAXN] , tmp_w[MAXN]; 
    int vis[MAXN]; 
     
    memset(vis , 0 , sizeof(vis)); 
    memset(dp , 0 , sizeof(dp)); 
    memcpy(tmp_l , l , sizeof(tmp_l)); 
    //排序從新存儲 
    sort(tmp_l , tmp_l+n); 
    for(int i  = 0 ; i < n ; i++){ 
        for(int j = 0 ; j < n ; j++){ 
            if(tmp_l[i] == l[j] && !vis[j]){ 
                tmp_w[i] = w[j] ; vis[j] = 1 ; break; 
            } 
        } 
    } 
    //求解最長上升子序列 
    int max_len = 1;//這裡一定要初始化為1 
    for(int i = 0 ; i < n ; i++){ 
        dp[i] = 1; 
        for(int j = i-1 ; j >= 0 ; j--){ 
            if(tmp_l[i] > tmp_l[j] && tmp_w[i] > tmp_w[j] && dp[j]+1 > dp[i]) 
                dp[i] = dp[j] + 1; 
            if(max_len < dp[i]) max_len = dp[i]; 
        }  
    } 
    printf("%d\n" , max_len); 
} 
 
int main(){ 
    //freopen("input.txt" , "r" , stdin); 
    int a , b; 
    scanf("%d" , &t); 
    while(t--){ 
        scanf("%d" , &n); 
        for(int i = 0 ; i < n ; i++){ 
            scanf("%d%d" , &a ,&b); 
            if(a > b){ l[i] = a ; w[i] = b;} 
            else { l[i] = b ; w[i] = a;} 
        } 
        solve(); 
    } 
    return 0; 
}