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);
    }
}

补充：软件开发 , C++ ,