subject 2075: Matrix nesting
time limit : 1Sec Memory limit : 128MB Submit : 259 solve : 54
Title Description
yes n A rectangle , Each rectangle can be used a,b To describe , Represents length and width . rectangle X(a,b) Can be nested in a rectangle Y(c,d) If and only if a <c,b<d perhaps b<c,a<d
（ It's like spinning 90 degree ）. for example （1,5） Can be nested in （6,2） within , But not nested in （3,4） in . Your task is to select as many rectangles as possible and line them up ,
So that except for the last one , Each rectangle can be nested in the next rectangle .
input
The first line is a positive number N(0<N<10), Indicates the number of test data groups .
The first line of each group of test data is a positive number n, Indicates the number of rectangles in the set of test data (n≤1000).
Subsequent n that 's ok , There are two numbers in each row a,b(0<a,b≤100), Represents the length and width of a rectangle .
output
Each group of test data output a number , Represents the maximum number of rectangles that meet the criteria , Each output occupies one line .
sample input
1
10
1 2
2 4
5 8
6 10
7 9
3 1
5 8
12 10
9 7
2 2
sample output
5
Thinking of solving problems
The nesting between rectangles is a binary relationship , The theory of adjacency matrix mapping is related , This graph should be directional , Because whether it can be included is unilateral , So we construct a digraph according to its properties . It can be concluded that , This is what we want （DAG） The longest path of .
State transfer equation : d(i)=max(d(j)+1|(i,j) belong to E） among E Is a set of edges
#include <stdio.h> #include <stdlib.h> #define MAX(a,b) ((a)>(b)?(a):(b))
// State transfer equation :d(i)=max(d(j)+1|(i,j) belong to E） among E Is a set of edges int arc[1001][1001]; int d[1001];
// Memory array , Remember to initialize to 0 void CreatGraph(int a[],int b[],int n) { int i,j; for(i=0;
i<n;i++) for(j=0;j<n;j++) // Two way, so not from i+1 start { if( (a[i]<a[j]&&b[i]<b[j]) || (b[i]<a[
j]&&a[i]<b[j])) // X(a,b)Y(c,d) a<c,b<d && a<d,b<c arc[i][j]=1; else arc[i][j]=0
; } } int dp(int i,int n) { int j; //int
&ans=d[i];//ans and d[i] Sharing one address ans And d[i] Is a variable c++ usage int *ans; ans=&d[i];
// use d Saved to i Is the longest path to the starting point if(*ans>0) return *ans; *ans=1; for(j=0;j<n;j++) if(arc[i][j
]) { *ans=MAX(*ans,dp(j,n)+1); //+1 Represents one more rectangle } return *ans; } int main() { int T;
scanf("%d",&T); while(T--) { int n,a[1001],b[1001],i,ans=0; scanf("%d",&n); for(
i=0;i<n;i++) d[i]=0; // initialization d for(i=0;i<n;i++) scanf("%d%d",&a[i],&b[i]);
CreatGraph(a,b,n); for(i=0;i<n;i++) ans=MAX(ans,dp(i,n)); // Each point can be used as a starting point printf(
"%d\n",ans); } return 0; }
Technology
Daily Recommendation