首页 > 代码库 > NYOJ16|嵌套矩形|DP|DAG模型|记忆化搜索
NYOJ16|嵌套矩形|DP|DAG模型|记忆化搜索
矩形嵌套
- 描述
- 有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
- 对于这道题目，我们可以有两种写法。
- 第一种写法：（DP+快速排序）
- 因为题目要我们选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内，而矩形又有长和宽两个因素。我们就可以开一个结构体来存储每一个
- 矩形的长和宽，读入时判断一下长和宽的大小，保证长小于宽，以便我们后边进行快速排序。接着快速排序一遍，写一个比较函数把每一个矩形的长按照从大到小排序。接下来我们
- 就可以直接DP了。
- 注意：MAX的初值应设为1，因为当没有矩形可以互相嵌套时，就不会触发if (NODE[k].A<NODE[j].A&&NODE[k].B<NODE[j].B)，自然也不会更新到MAX值。而当没有矩形可以互相
- 嵌套时，符合条件的矩形数为1，所以MAX初值应该设置为1，这样才可以保证输出的答案是有效的。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 using namespace std; 7 int read() 8 { 9 int f=1,x=0; char c=getchar(); 10 while (c>‘9‘||c<‘0‘) {if (c==‘-‘) f=-1; c=getchar();} 11 while (c>=‘0‘ && c<=‘9‘) {x=x*10+c-‘0‘; c=getchar();} 12 return x*f; 13 } 14 struct node 15 { 16 int A; 17 int B; 18 }NODE[1110]; 19 bool comp(const node&a,const node&b) 20 { 21 if (a.A==b.A) return a.B<b.B; 22 return a.A<b.A; 23 } 24 int T,N,F[1110],MAX; 25 int main() 26 { 27 T=read(); 28 for (int i=1; i<=T; i++) { 29 MAX=1; 30 N=read(); 31 for (int j=1; j<=N; j++) F[j]=1; 32 for (int j=1; j<=N; j++) { 33 NODE[j].A=read(); 34 NODE[j].B=read(); 35 if (NODE[j].A>NODE[j].B) { 36 int t=NODE[j].A; 37 NODE[j].A=NODE[j].B; 38 NODE[j].B=t; 39 } 40 } 41 sort(NODE+1,NODE+N+1,comp); 42 for (int j=2; j<=N; j++) 43 for (int k=1; k<j; k++) 44 if (NODE[k].A<NODE[j].A&&NODE[k].B<NODE[j].B) { 45 if (F[k]+1>F[j]) F[j]=F[k]+1; 46 if (F[j]>MAX) MAX=F[j]; 47 } 48 printf("%d\n",MAX); 49 } 50 return 0; 51 }
第二种写法：（DP+DAG模型+记忆化搜索）
Tips:DAG:有向无环图。由于一个矩形无法直接或间接地嵌套到自己的内部，所以这个有向图是无环的。
这种写法是紫书上推荐的，所以网络上的代码大多是这种写法。我们还是开一个结构体来存储每一个矩形的长和宽，然后就两重循环枚举每两个矩形之间是否可以嵌套，如果可以嵌套，
就将G[i][j]标记为1，意味着i到j有边相连。然后DFS记忆化搜索每一个矩形（实际上就是每一个点，因为我们已经把矩形间的嵌套关系建模成DAG了，自然每一个矩形都变成了DAG中的
每一个点。），我这里用的DFS是有返回值的，而不是一个纯过程，DFS(NUM)返回的是从NUM点出发的最长路径，也就是最多可以嵌套的矩形个数。然后找出最长路径，记录下来，就
是答案了。
我这里还是想讲一讲这个记忆化搜索的函数，打一下批注以助于理解。
int DFS(int NUM)//寻找NUM点出发的最长路径
{
int SP=1;//注意：SP要定义在函数里，这样子两层递归之间的SP才不会互相伤害。 SP用于记录当层NUM点出发的最长路径长度。
if (BOOK[NUM]>0) return BOOK[NUM];//BOOK[NUM]存储着NUM点出发的最长路径。如果BOOK[NUM]>0，这就意味着NUM点出发的最长路径已经被确定了，也就没有必要继续搜索
NUM点出发的最长路径了，就直接返回NUM点出发的最长路径，作为上一层需要的答案组成之一。
for (int i=1; i<=N; i++)
if (G[NUM][i]) SP=la(SP,DFS(i)+1);//如果NUM点和i点之间是连通的，SP=max(SP,DFS(i)+1)，这一点运用的思想与DP一样，不作解释。
BOOK[NUM]=SP;//搜索完当层NUM点出发的最长路径，就标记下去。
return SP;
}
记忆化搜索的核心就是标记和搜索，标记已经搜索过的部分和内容，下一次再到这里时就不需要再耗时搜索一遍，因为结果已经确定了，所以直接返回结果就可以。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 using namespace std; 7 int read() 8 { 9 int f=1,x=0; char c=getchar(); 10 while (c>‘9‘||c<‘0‘) {if (c==‘-‘) f=-1; c=getchar();} 11 while (c>=‘0‘ && c<=‘9‘) {x=x*10+c-‘0‘; c=getchar();} 12 return x*f; 13 } 14 struct node 15 { 16 int A; 17 int B; 18 }NODE[1110]; 19 int T,N,MAX=1,F[1100],SP; 20 bool G[1100][1100]; 21 int BOOK[1100]; 22 int la(int A,int B) 23 { 24 if (A>B) return A; 25 return B; 26 } 27 int DFS(int NUM) 28 { 29 int SP=1; 30 if (BOOK[NUM]>0) return BOOK[NUM]; 31 for (int i=1; i<=N; i++) 32 if (G[NUM][i]) SP=la(SP,DFS(i)+1); 33 BOOK[NUM]=SP; 34 return SP; 35 } 36 int main() 37 { 38 T=read(); 39 while (T--) { 40 MAX=1; 41 memset(BOOK,0,sizeof(BOOK)); 42 memset(G,0,sizeof(G)); 43 N=read(); 44 for (int i=1; i<=N; i++) { 45 NODE[i].A=read(); NODE[i].B=read(); 46 } 47 for (int i=1; i<=N; i++) 48 for (int j=1; j<=N; j++) 49 if ((NODE[i].A<NODE[j].A&&NODE[i].B<NODE[j].B)|| 50 (NODE[i].A<NODE[j].B&&NODE[i].B<NODE[j].A)) G[i][j]=1; 51 for (int i=1; i<=N; i++) 52 if (DFS(i)>MAX) MAX=DFS(i); 53 printf("%d\n",MAX); 54 } 55 return 0; 56 }
有问题可以直接在评论里面提问，有需要转载的请得到我的允许，否则按侵权处理。
NYOJ16|嵌套矩形|DP|DAG模型|记忆化搜索