矩形嵌套
- 描述
- 有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，这样才可以保证输出的答案是有效的。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int read()
{
int f=,x=; char c=getchar();
while (c>''||c<'') {if (c=='-') f=-; c=getchar();}
while (c>='' && c<='') {x=x*+c-''; c=getchar();}
return x*f;
}
struct node
{
int A;
int B;
}NODE[];
bool comp(const node&a,const node&b)
{
if (a.A==b.A) return a.B<b.B;
return a.A<b.A;
}
int T,N,F[],MAX;
int main()
{
T=read();
for (int i=; i<=T; i++) {
MAX=;
N=read();
for (int j=; j<=N; j++) F[j]=;
for (int j=; j<=N; j++) {
NODE[j].A=read();
NODE[j].B=read();
if (NODE[j].A>NODE[j].B) {
int t=NODE[j].A;
NODE[j].A=NODE[j].B;
NODE[j].B=t;
}
}
sort(NODE+,NODE+N+,comp);
for (int j=; j<=N; j++)
for (int k=; k<j; k++)
if (NODE[k].A<NODE[j].A&&NODE[k].B<NODE[j].B) {
if (F[k]+>F[j]) F[j]=F[k]+;
if (F[j]>MAX) MAX=F[j];
}
printf("%d\n",MAX);
}
return ;
}
矩形嵌套
第二种写法：（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;
}
记忆化搜索的核心就是标记和搜索，标记已经搜索过的部分和内容，下一次再到这里时就不需要再耗时搜索一遍，因为结果已经确定了，所以直接返回结果就可以。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int read()
{
int f=,x=; char c=getchar();
while (c>''||c<'') {if (c=='-') f=-; c=getchar();}
while (c>='' && c<='') {x=x*+c-''; c=getchar();}
return x*f;
}
struct node
{
int A;
int B;
}NODE[];
int T,N,MAX=,F[],SP;
bool G[][];
int BOOK[];
int la(int A,int B)
{
if (A>B) return A;
return B;
}
int DFS(int NUM)
{
int SP=;
if (BOOK[NUM]>) return BOOK[NUM];
for (int i=; i<=N; i++)
if (G[NUM][i]) SP=la(SP,DFS(i)+);
BOOK[NUM]=SP;
return SP;
}
int main()
{
T=read();
while (T--) {
MAX=;
memset(BOOK,,sizeof(BOOK));
memset(G,,sizeof(G));
N=read();
for (int i=; i<=N; i++) {
NODE[i].A=read(); NODE[i].B=read();
}
for (int i=; i<=N; i++)
for (int j=; j<=N; j++)
if ((NODE[i].A<NODE[j].A&&NODE[i].B<NODE[j].B)||
(NODE[i].A<NODE[j].B&&NODE[i].B<NODE[j].A)) G[i][j]=;
for (int i=; i<=N; i++)
if (DFS(i)>MAX) MAX=DFS(i);
printf("%d\n",MAX);
}
return ;
}
嵌套矩形
有问题可以直接在评论里面提问，有需要转载的请得到我的允许，否则按侵权处理。