題目描述

有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

WA：運行錯誤50% ，不清楚原因...

#include <iostream> #include <algorithm> using namespace std;const int maxn = 1010; const int inf = 1000000000; struct node {int a, b; }Node[maxn];int G[maxn][maxn]; int dp[maxn]; int N; //測試組數 int n; //含有矩形個數 int ans = -1;int DP(int i) {if(dp[i] > 0) return dp[i];dp[i] = 1;for(int j = 1; j <= n; j++){if(G[i][j] != inf){int temp = DP(j) + G[i][j];if(temp > dp[i]){dp[i] = temp;}}}return dp[i]; }int main() {scanf("%d", &N);while(N--){//輸入scanf("%d", &n);fill(G[0], G[0]+maxn*maxn, inf);fill(dp, dp+maxn, 0);for(int i = 1; i <= n; i++){scanf("%d%d", &Node[i].a, &Node[i].b);if(Node[i].a > Node[i].b) swap(Node[i].a, Node[i].b);}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if( (Node[i].a < Node[j].a && Node[i].b < Node[j].b)){G[i][j] = 1;}}}for(int i = 1; i <= n; i++){ans = max(ans, DP(i));}printf("%d\n", ans);}return 0;}

?

別人的代碼：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=1e3+10; int G[maxn][maxn]; struct node {int x,y; }; node a[1001]; int d[1001]; int n; bool cmp(node a,node b) {if(a.x<=b.x) return 1;else if(a.x==b.x&&a.y<=b.y) return 1;else return 0; } void creat() {memset(G,0,sizeof(G));for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)if(a[i].x<a[j].x&&a[i].y<a[j].y) G[i][j]=1; } int dp(int i) {if(d[i]>0) return d[i];d[i]=1;for(int j=1;j<=n;j++){if(G[i][j]==1){int t=dp(j);d[i]=max(d[i],t+1);}}return d[i]; } int main() {int _;scanf("%d",&_);while(_--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&a[i].x,&a[i].y);if(a[i].x>a[i].y) swap(a[i].x,a[i].y);}//sort(a+1,a+1+n,cmp);memset(d,0,sizeof(d));creat();int mx=0;for(int i=1;i<=n;i++){int t=dp(i);mx=max(mx,t);}printf("%d\n",mx);} } 上面那個代碼是不是比較難理解，那看看下面這個優化的代碼，是不是感覺很神奇的感覺。如此完美的優化了先將矩形從大到小排序，然后dp[i]代表當前i的最長矩形嵌套長度為多少。#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int maxn=1e3+10; int G[maxn][maxn]; struct node {int x,y; }; node a[1001]; int dp[1001]; int n; bool cmp(node a,node b) {if(a.x==b.x) return a.y>b.y;return a.x>b.x; }int main() {int _;scanf("%d",&_);while(_--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&a[i].x,&a[i].y);if(a[i].x>a[i].y) swap(a[i].x,a[i].y);}sort(a+1,a+1+n,cmp);memset(dp,0,sizeof(dp));int ans=0;for(int i=1;i<=n;i++){dp[i]=1;for(int j=1;j<i;j++){if(a[i].x<a[j].x&&a[i].y<a[j].y){dp[i]=max(dp[i],dp[j]+1);}}ans=max(ans,dp[i]);}cout<<ans<<endl;} } --------------------- 作者：ccsu_deer 來源：CSDN 原文：https://blog.csdn.net/qq_41286356/article/details/85043571 版權聲明：本文為博主原創文章，轉載請附上博文鏈接！

?

總結

以上是生活随笔為你收集整理的Codeup-问题 A: 问题 A: 矩形嵌套的全部內容，希望文章能夠幫你解決所遇到的問題。

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