/********************************************************************@file     Main_practise.cpp@date     2014-9-24@author   Tiger@brief    动态规划@details  矩形嵌套问题********************************************************************/#include <cstdio>#include <algorithm>typedef struct Rectangle{    int m_nLen;    int m_nWid;}RECT, *PRECT;#define MAX_N 1005int Memo[MAX_N][MAX_N];int DP[MAX_N];bool isIn(RECT left_rect, RECT right_rect);int dp(int i, int nMax);int main(int argc, const char* argv[]){    int nTestCases = 0;    scanf("%d", &nTestCases);        while (nTestCases--)    {        int nRectCnt = 0;        scanf("%d", &nRectCnt);        int nLen = 0, nWid = 0;        PRECT RectArray = new RECT[nRectCnt];        for (int i=0; i<nRectCnt; ++i)        {            scanf("%d%d", &nLen, &nWid);            RectArray[i].m_nLen = nLen;            RectArray[i].m_nWid = nWid;            DP[i] = 0;            for (int j=0; j<nRectCnt; ++j)            {                Memo[i][j] = 0;            }        }                for (int i=0; i<nRectCnt; ++i)        {            for (int j=0; j<nRectCnt; ++j)            {                if (isIn(RectArray[i], RectArray[j]))                {                    Memo[i][j] = 1;                }            }        }        int nMax = 0;        for (int i=0; i<nRectCnt; ++i)        {            nMax = std::max(nMax, dp(i, nRectCnt));        }        printf("%d\n", nMax);        delete [] RectArray;    }    return 0;}bool isIn(RECT left_rect, RECT right_rect){    return (left_rect.m_nWid > right_rect.m_nWid && left_rect.m_nLen > right_rect.m_nLen)        || (left_rect.m_nWid > right_rect.m_nLen && left_rect.m_nLen > right_rect.m_nWid);}int dp(int i, int nMax){    if (DP[i] > 0)    {        return DP[i];    }    else    {        DP[i] = 1;        for (int j=0; j<nMax; ++j)        {            if (Memo[i][j])            {                DP[i] = std::max(DP[i], dp(j, nMax)+1);            }        }        return DP[i];    }}