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
解题思路：     1   DP最长的上升子序列
                       2   题目说了，矩形是可以旋转90度的，那么长和宽就是可以随便的更改，根据贪心的思想，我们知道如果要得到最多的矩形嵌套，那么长和宽的大小排序很重要，就是说尽量满足矩形都能够排成一个序列，这样就能够满足最多的矩形嵌套，所以我么输入数据的时候，让大的一个作为长，小的作为宽，那么我们对长度进行排序，然后在从宽里面查找最长的上升子序列即可

代码：
[cpp] 
#include <algorithm> 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <vector> 
#include <cstdio> 
#include <stack> 
#include <queue> 
#include <set> 
using namespace std; 
#define MAXN 1010 
 
int t , n; 
int l[MAXN] , w[MAXN]; 
int dp[MAXN]; 
 
void solve(){ 
    int tmp_l[MAXN] , tmp_w[MAXN]; 
    int vis[MAXN]; 
     
    memset(vis , 0 , sizeof(vis)); 
    memset(dp , 0 , sizeof(dp)); 
    memcpy(tmp_l , l , sizeof(tmp_l)); 
    //排序从新存储 
    sort(tmp_l , tmp_l+n); 
    for(int i  = 0 ; i < n ; i++){ 
        for(int j = 0 ; j < n ; j++){ 
            if(tmp_l[i] == l[j] && !vis[j]){ 
                tmp_w[i] = w[j] ; vis[j] = 1 ; break; 
            } 
        } 
    } 
    //求解最长上升子序列 
    int max_len = 1;//这里一定要初始化为1 
    for(int i = 0 ; i < n ; i++){ 
        dp[i] = 1; 
        for(int j = i-1 ; j >= 0 ; j--){ 
            if(tmp_l[i] > tmp_l[j] && tmp_w[i] > tmp_w[j] && dp[j]+1 > dp[i]) 
                dp[i] = dp[j] + 1; 
            if(max_len < dp[i]) max_len = dp[i]; 
        }  
    } 
    printf("%d/n" , max_len); 
} 
 
int main(){ 
    //freopen("input.txt" , "r" , stdin); 
    int a , b; 
    scanf("%d" , &t); 
    while(t--){ 
        scanf("%d" , &n); 
        for(int i = 0 ; i < n ; i++){ 
            scanf("%d%d" , &a ,&b); 
            if(a > b){ l[i] = a ; w[i] = b;} 
            else { l[i] = b ; w[i] = a;} 
        } 
        solve(); 
    } 
    return 0; 
} 

作者；cgl1079743846