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

一道有意思的动归题，然而不安分的我想尝试用用别的方法做，于是写了一个WA的代码，感觉上是挺对的，可是细细品味，发现一个致命的错误。
错误代码如下（C）：

//问题代码，此写法有点像贪心，存在后效应性，需要用动态规划取消后效应性
//从大到小开始查找，这里我们选择的不是尺寸最大的，而是可以包含（嵌套）矩形数最多的
//#include <stdio.h>
//#define MAX(a, b) a > b ? a : b
//#define MAXSIZEN 1001
//int t[MAXSIZEN] = {0};
//int ans;
//typedef struct
//{
   
// int a;
// int b;
//} rec; //矩形
//rec R[MAXSIZEN];
//
////检索小于a[i]和b[i]的最大矩形对应的t[j]
//void retrieve(int p, int n)
//{
   
// int q, i;
// q = 0;
// for(i = 1; i <= n; i++)
// {
   
// if(R[p].a > R[i].a && R[p].b > R[i].b)
// {
   
// if(t[i] > t[q])
// {
   
// q = i;
// }
// }
// }
// ans++;
// if(t[q])
// {
   
// retrieve(q, n);
// }
//}
//
//int main(int argc, const char * argv[])
//{
   
// int N;
// scanf("%d", &N);
// 
// while (N--)
// {
   
// ans = 1;
// int n, a, b;
// scanf("%d", &n);
// for (int i = 1; i <= n; i++)
// {
   
// scanf("%d %d", &a, &b);
// //调整矩形方向
// if (a > b)
// {
   
// R[i].a = b;
// R[i].b = a;
// }
// else
// {
   
// R[i].a = a;
// R[i].b = b;
// }
// }
// 
// int p = 0;
// for(int i = 1; i <= n; i++)
// {
   
// for(int j = 1; j <= n; j++)
// {
   
// if(R[i].a > R[j].a && R[i].b > R[j].b)
// {
   
// t[i]++;
// }
// }
// if(t[i] > t[p])
// {
   
// p = i;
// }
// }
// 
// retrieve(p, n);
// 
// printf("%d\n", ans);
// }
//
// 
// return 0;
//}

这种方法偏向于贪心算法，可是我忽略了最重要的问题，贪心算法不能存在后效应性，而我的写法却完美的撞上了这个问题！！！

所以，只有另觅动归了……

//动归
#include <stdio.h>
#include <string.h>
#define MAX(a, b) a > b ? a : b
#define MAXSIZEN 1001
int dp[MAXSIZEN];   //dp[i]当排好序的前i个矩形符合条件的包括第i个时的最大值
int ans;
typedef struct
{
    int a;
    int b;
} rec;  //矩形

int main(int argc, const char * argv[])
{
    int N;
    scanf("%d", &N);
    rec R[MAXSIZEN];

    while (N--)
    {
        ans = 1;
        memset(dp, 0, sizeof(dp));
        int n, a, b;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d %d", &a, &b);
            //调整矩形方向
            if (a > b)
            {
                R[i].a = b;
                R[i].b = a;
            }
            else
            {
                R[i].a = a;
                R[i].b = b;
            }
        }

        //按一条边排序
        for (int i = 1; i < n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                if (R[i].a > R[j].a || (R[i].a == R[j].a && R[i].b > R[j].b))
                {
                                        R[i].a ^= R[j].a;
                                        R[j].a ^= R[i].a;
                                        R[i].a ^= R[j].a;
// R[i].a ^= R[j].a ^= R[i].a ^= R[j].a;
                                        R[i].b ^= R[j].b;
                                        R[j].b ^= R[i].b;
                                        R[i].b ^= R[j].b;
// R[i].b ^= R[j].b ^= R[i].b ^= R[j].b;
                }
            }
        }

        int flag;
        for (int i = 1; i <= n; i++)
        {
            dp[i] = 1;
            flag = 0;
            for (int j = 1; j < i; j++)
            {
                if (R[j].a < R[i].a && R[j].b < R[i].b && dp[j] > flag)
                {
                    flag = dp[j];
                }
            }
            dp[i] += flag;
        }

        for (int i = 1; i <= n; i++)
        {
            if (ans < dp[i])
            {
                ans = dp[i];
            }
        }

        printf("%d\n", ans);
    }

    return 0;
}

AC代码，哦耶+_+!!!