描述

有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---N個矩陣，如果第一個矩陣可以包含第I個矩陣，并且滿足第i個矩陣最多矩陣列小于等于第一個矩陣那么更新第I個矩陣，使得A[i]=A[1]+1;對于其他2...N個矩陣也可以這樣操作。

1 //觀察是否滿足矩形P1，在矩形P2內部 2 public static bool IsMatch(rectAngle p1, rectAngle p2) 3 { 4 bool flag = (p1.getX() < p2.getX() && p1.getY() < p2.getY()) || (p1.getX() < p2.getY() && p1.getY() < p2.getX()); 5 return flag; 6 } 7 8 public static int HaveRectangleCount(List<rectAngle> P) 9 { 10 int[,] M = new int[P.Count, P.Count]; 11 int[] dp = new int[P.Count]; 12 int biggest = 0; 13 for (int k = 0; k < P.Count; k++) 14 dp[k] = 1; 15 rectAngle[] x = new rectAngle[P.Count + 1]; 16 x[0] = new rectAngle(0, 0); 17 //解法一 18 for (int i = 0; i < P.Count; i++) 19 { 20 for (int j = count; j >= 0; j--) 21 { 22 if (IsMatch(x[j], P[i])) 23 { 24 x[j + 1] = new rectAngle(P[i].getX(), P[i].getY()); 25 if (j == count) 26 count++; 27 break; 28 } 29 } 30 } 31 outPutrectAngle(x.ToList<rectAngle>(), count);//輸出一個滿足條件的矩陣例子 32 Console.WriteLine("count=" + count); 33 34 35 //解法二、不斷搜索，更新其排位表 36 for (int i = 0; i < P.Count; i++) 37 { 38 for (int j = 0; j < P.Count; j++) 39 { 40 if (IsMatch(P[i], P[j]) && (dp[i] >= dp[j])) 41 dp[j] = dp[i] + 1; 42 Console.Write(dp[j] + " ");//輸出此時的每個元素的排位，觀察其變化過程。 43 } 44 Console.WriteLine(); 45 } 46 47 for (int i = 0; i < P.Count; i++) 48 { 49 if (dp[i] > biggest) 50 biggest = dp[i]; 51 } 52 return biggest; 53 } 54 55 public static void outPutrectAngle(List<rectAngle> P, int Len) 56 { 57 for (int i = 1; i <= Len; i++) 58 { 59 Console.Write("x=" + P[i].getX() + ",y=" + P[i].getY() + ", "); 60 } 61 Console.WriteLine(); 62 } View Code

?

轉載于:https://www.cnblogs.com/xiaoyi115/p/3175932.html

總結

以上是生活随笔為你收集整理的矩形嵌套 南阳理工ACM的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。