Contents

1. 1. 题目：
2. 2. 分析：

• 动态规划

题目：

　　有n个矩形，每个矩形可以用a,b来描述，表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d（相当于旋转X90度）。例如（1,5）
可以嵌套在（6,2）内，但不能嵌套在（3,4）中。你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内。

分析：

　　先给矩形按x排个序，此时是关于x的递增序列，然后用求最长上升子序列的方法求解，只是把if里的条件改为了arr[j].x < arr[i].x && arr[j].y < arr[i].y

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;

const int N = 1001;

struct node{
    int x;
    int y;
};

node arr[N];
int dp[N];

bool cmp(node a, node b){

    if(a.x < b.x)
        return 1;
    else
        return 0;
}

int main(){

    freopen("input.txt", "r", stdin);
    int T, n;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            scanf("%d%d", &arr[i].x, &arr[i].y);
            if(arr[i].x > arr[i].y){
                swap(arr[i].x, arr[i].y);
            }
        }
        sort(arr, arr + n, cmp);
        memset(dp, 0, sizeof(dp));
        //用求最长上升子序列的方法
        for(int i = 0; i < n; i++){
            for(int j = 0; j <= i; j++){
                if(arr[j].x < arr[i].x && arr[j].y < arr[i].y){
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        int maxs = dp[0];
        for(int i = 1; i < n; i++){
            if(dp[i] > maxs)
                maxs = dp[i];
        }
        //dp初始化时是0，没把自己算进去
        printf("%d\n", maxs + 1);
    }
    return 0;
}