矩形嵌套
时间限制：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
View Code
1 //wa 2 //贪心思想wa，反例：<100 ,1> <9 6> <8 3>正确答案是2，若按下面的贪心思想则答案是0 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 using namespace std; 7 typedef struct Node 8 { 9int length,width;10 }Node;11 Node ch[1005];12 int cmp(const void *a,const void *b)13 {14Node *c = (Node *)a;15Node *d = (Node *)b;16if(c->length!=d->length)17 return d->length - c->length;18else19 return d->width - c->width;20 }21 int main()22 {23int i,j,k,t,T;24cin>>T;25int num,a,b;26while(T--)27{28 memset(ch,0,sizeof(ch));29 cin>>num;30 if(num==0)31 {32 cout<<0<<endl;33 continue;34 }35 for(i=1;i<=num;i++)36 {37 cin>>a>>b;38 if(a<b)39 {40 a^=b;41 b^=a;42 a^=b;43 }44 ch[i].length = a,ch[i].width = b;45 }46 if(num==1)47 {48 cout<<1<<endl;49 continue;50 }51 qsort(&ch[i],num,sizeof(Node),cmp);52 int cnt = 1;//不是0 53 for(i=1;i<=num;i++)54 if(ch[i].length>=ch[i+1].length&&ch[i].width>=ch[i+1].width)55 cnt++;56 cout<<cnt<<endl;57}58return 0;59 }
1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 using namespace std; 5 typedef struct Node 6 { 7int length,width; 8 }Node; 9 Node ch[1005];10 int f[1005];11 int cmp(const void *a,const void *b)12 {13Node *c = (Node *)a;14Node *d = (Node *)b;15if(c->length!=d->length)16 return d->length - c->length;17else18 return d->width - c->width;19 }20 int main()21 {22int i,j,k,t,T;23cin>>T;24int num,a,b;25while(T--)26{27 memset(ch,0,sizeof(ch));28 cin>>num;29 if(num==0)30 {31 cout<<0<<endl;32 continue;33 }34 for(i=1;i<=num;i++)35 {36 cin>>a>>b;37 if(a<b)38 {39 a^=b;40 b^=a;41 a^=b;42 }43 ch[i].length = a,ch[i].width = b;44 f[i] = 1;45 }46 if(num==1)47 {48 cout<<1<<endl;49 continue;50 }51 qsort(&ch[1],num,sizeof(Node),cmp);52 int max = 0;53 for(i=2;i<=num;i++)54 {55 for(j=i-1;j>=1;j--)56 if(ch[i].length<ch[j].length&&ch[i].width<ch[j].width)//没有等于 57 //f[i] >?= f[j] + 1;58 if(f[i]<(f[j]+1))59 f[i] = f[j] + 1;60 if(max < f[i])61 max = f[i];62 }63 cout<<max<<endl;64}65return 0;66 }
