首页 > 代码库 > NYOJ 16 矩形嵌套

NYOJ 16 矩形嵌套

2024-07-11 21:20:24   220人阅读

矩形嵌套

时间限制：3000 ms  |  内存限制：65535 KB
难度：4
 
描述
有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)，表示矩形的长和宽
输出
每组测试数据都输出一个数，表示最多符合条件的矩形数目，每组输出占一行
样例输入
1101 22 45 86 107 93 15 812 109 72 2
样例输出
5
来源
经典题目
上传者
张云聪

解题：排序，dp。。。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <algorithm> 8 #include <cmath> 9 #define LL long long10 using namespace std;11 struct rectangle {12     int x,y;13 } R[1010];14 int dp[1010];15 bool cmp(const rectangle &a,const rectangle &b) {16     if(a.x < b.x || a.x == b.x && a.y <= b.y) return true;17     return false;18 }19 int main() {20     int ks,n,i,j,mx,ans;21     scanf("%d",&ks);22     while(ks--) {23         scanf("%d",&n);24         for(i = 0; i < n; i++) {25             scanf("%d %d",&R[i].x,&R[i].y);26             if(R[i].x > R[i].y) swap(R[i].x,R[i].y);27         }28         sort(R,R+n,cmp);29         memset(dp,0,sizeof(dp));30         ans = dp[0] = 1;31         for(i = 1; i < n; i++) {32             for(mx = j = 0; j < i; j++)33                 if(R[j].x < R[i].x && R[j].y < R[i].y && mx < dp[j]) mx = dp[j];34             dp[i] = mx+1;35             if(dp[i] > ans) ans = dp[i];36         }37         printf("%d\n",ans);38     }39     return 0;40 }
View Code

 


联系
我们