沈阳哪家做网站最好,信息技术制作网站首页,利用jquery做音乐网站,wordpress带灯箱的主题矩形嵌套 时间限制#xff1a;3000 ms | 内存限制#xff1a;65535 KB难度#xff1a;4描述有n个矩形#xff0c;每个矩形可以用a,b来描述#xff0c;表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当ac,bd或者bc,ad#xff08;相当于旋转X90度3000 ms | 内存限制65535 KB 难度4 描述有n个矩形每个矩形可以用a,b来描述表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当ac,bd或者bc,ad相当于旋转X90度。例如1,5可以嵌套在6,2内但不能嵌套在3,4中。你的任务是选出尽可能多的矩形排成一行使得除最后一个外每一个矩形都可以嵌套在下一个矩形内。 输入第一行是一个正正数N(0N10)表示测试数据组数 每组测试数据的第一行是一个正正数n表示该组测试数据中含有矩形的个数(n1000) 随后的n行每行有两个数a,b(0a,b100)表示矩形的长和宽输出每组测试数据都输出一个数表示最多符合条件的矩形数目每组输出占一行样例输入 1
10
1 2
2 4
5 8
6 10
7 9
3 1
5 8
12 10
9 7
2 2样例输出 5 #include stdio.h
#include string.h
#define N 100010
int a[N][2];
int b[N];int main()
{int n,m,result;int i,j,temp,temp1,max;scanf(%d,n);while(n--){scanf(%d,m);for(i1;im;i) //读入测试数据 {scanf(%d%d,temp,temp1); a[i][0]temptemp1?temp:temp1; //矩形的宽 a[i][1]temptemp1?temp1:temp; //矩形的长 } for(i1;im;i) //对矩形的宽进行由小到大排序 for(ji1;jm;j) if(a[i][0]a[j][0]){tempa[i][0];a[i][0]a[j][0];a[j][0]temp; temp1a[i][1];a[i][1]a[j][1];a[j][1]temp1;}//求长进行最长升序列求解 memset(b,0,sizeof(b)); result0;for(im;i0;i--){max0;for(ji1;jm;j)if(a[j][1]a[i][1] a[j][0]a[i][0]) maxmaxb[j]?max:b[j];b[i]max1;resultresultb[i]?result:b[i];} printf(%d\n,result); }return 0;
}
