NYOJ16——矩形嵌套

題目分析：實際上這個題和HDU上的一道題是一樣的。不過這裡針對每一個矩形，只需要分別把長、寬和寬、長組成的矩形放入數組中進行考慮，相對來說這道題要簡單一些。

[cpp]
#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
 
typedef struct  
{ 
    int w; 
    int h; 
}RECT; 
 
RECT rect[2000]; 
int dp[2000]; 
 
int compare(const void *a, const void *b) 
{ 
    RECT *p1 = (RECT *)a; 
    RECT *p2 = (RECT *)b; 
    if(p1->w == p2->w) 
        return p1->h - p2->h; 
    else 
        return p1->w - p2->w; 
} 
 
int max(const int a, const int b) 
{ 
    return a > b ? a : b; 
} 
 
int DP(int n) 
{ 
    int i,j; 
    dp[0] = 1; 
    int ans = 1; 
    for(i = 1; i < n; ++i) 
    { 
        dp[i] = 1; 
        for(j = 0; j < i; ++j) 
        { 
            if(rect[j].w < rect[i].w && rect[j].h < rect[i].h) 
                dp[i] = max(dp[i],dp[j] + 1); 
        } 
        ans = max(ans,dp[i]); 
    } 
    return ans; 
} 
 
int main() 
{ 
    int t,n; 
    int i,k; 
    int ans; 
    scanf("%d",&t); 
    while(t--) 
    { 
        scanf("%d",&n); 
        for(i = 0,k = 0; i < n; ++i,++k) 
        { 
            scanf("%d %d",&rect[k].w,&rect[k].h); 
            if(rect[k].w != rect[k].h) 
            { 
                rect[k + 1].w = rect[k].h; 
                rect[k + 1].h = rect[k].w; 
                ++k; 
            } 
        } 
        n = k; 
        qsort(rect, n, sizeof(rect[0]),compare); 
        ans = DP(n); 
        printf("%d\n",ans); 
    } 
}