矩形嵌套 時間限制：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)，表示矩形的長和寬 輸出 每組測試數據都輸出一個數，表示最多符合條件的矩形數目，每組輸出占一行 樣例輸入 1 10 1 2 2 4 5 8 6 10 7 9 3 1 5 8 12 10 9 7 2 2 樣例輸出 5來源 經典題目 [cpp] /********************************* * 日期：2013-3-26 * 作者：SJF0115 * 題號: 題目16: 矩形嵌套 * 來源：http://acm.nyist.net/JudgeOnline/problem.php?pid=16 * 結果：AC * 來源：南陽理工OJ * 總結： **********************************/ #include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct Rec{ int MaxL; int MinL; }Rec; int cmp(const void *a,const void *b){ struct Rec* c = (Rec* )a; struct Rec* d = (Rec* )b; return c->MaxL - d->MaxL; } int main () { int N,M,a,b,i,j; Rec rec[1010]; int dp[1010]; //freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin); scanf("%d",&N); while (N--){ scanf("%d",&M); //初始化 for(i = 0;i < M;i++){ scanf("%d %d",&a,&b); if(a < b){ rec[i].MaxL = b; rec[i].MinL = a; } else{ rec[i].MaxL = a; rec[i].MinL = b; } } //按最大邊排序 qsort(rec,M,sizeof(rec[0]),cmp); //初始化數組dp memset(dp,0,sizeof(dp)); for(i = 0;i < M;i++){ dp[i] = 1; for(j = 0;j < i;j++){ if(rec[i].MaxL > rec[j].MaxL && rec[i].MinL > rec[j].MinL){ if(dp[i] < dp[j] + 1){ dp[i] = dp[j] + 1; } } } } //輸出 int Max = 0; for(i = 0;i < M;i++){ if(dp[i] > Max){ Max = dp[i]; } } printf("%d\n",Max); } return 0; } /********************************* * 日期：2013-3-26 * 作者：SJF0115 * 題號: 題目16: 矩形嵌套 * 來源：http://acm.nyist.net/JudgeOnline/problem.php?pid=16 * 結果：AC * 來源：南陽理工OJ * 總結： **********************************/ #include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct Rec{ int MaxL; int MinL; }Rec; int cmp(const void *a,const void *b){ struct Rec* c = (Rec* )a; struct Rec* d = (Rec* )b; return c->MaxL - d->MaxL; } int main () { int N,M,a,b,i,j; Rec rec[1010]; int dp[1010]; //freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin); scanf("%d",&N); while (N--){ scanf("%d",&M); //初始化 for(i = 0;i < M;i++){ scanf("%d %d",&a,&b); if(a < b){ rec[i].MaxL = b; rec[i].MinL = a; } else{ rec[i].MaxL = a; rec[i].MinL = b; } } //按最大邊排序 qsort(rec,M,sizeof(rec[0]),cmp); //初始化數組dp memset(dp,0,sizeof(dp)); for(i = 0;i < M;i++){ dp[i] = 1; for(j = 0;j < i;j++){ if(rec[i].MaxL > rec[j].MaxL && rec[i].MinL > rec[j].MinL){ if(dp[i] < dp[j] + 1){ dp[i] = dp[j] + 1; } } } } //輸出 int Max = 0; for(i = 0;i < M;i++){ if(dp[i] > Max){ Max = dp[i]; } } printf("%d\n",Max); } return 0; }
