【题目描述】
有n个矩形，每个矩形可以用a,b来描述，表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d（相当于旋转X90度）。例如（1,5）可以嵌套在（6,2）内，但不能嵌套在（3,4）中。你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内。如果有多解，矩形编号的字典序应尽量小。 【分析】 矩形之间的"可嵌套"关系是一个典型的二元关系，二元关系可以用图来建模。如果矩形X可以嵌套在矩形Y里，我们就从X到Y连一条有向边。这个有向图是无环的，因为一个矩形无法直接或间接地嵌套在自己的内部。换句话说，它是一个DAG。这样，我们的任务便是求DAG上的最长路径。  //状态：d(i)表示从节点（矩形）i出发的最长路长度（节点个数，即矩形个数） //状态转移方程：d(i)=max{d(j)+1|graph[i][j]=1} #include<iostream> #include<cstring> using namespace std; const int maxn=1005; //矩形 typedef struct{ int length; int width; }rectangle; rectangle rec[maxn];//矩形数组 int graph[maxn][maxn];//图 int n;//矩形个数 int d[maxn];//d数组初始化为0，因为d[i]至少是1，初始化一个不影响d[i]的非正数即可 int path[maxn];//打印所有路径的时候用,path[i]最长路径上第i个点 void read(){ int x,y; cin>>n; for(int i=0;i<n;i++){ cin>>x>>y; rec[i].length=(x>y?x:y); rec[i].width=(x>y?y:x); } } void createGraph(){ memset(graph,0,sizeof(graph)); for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(rec[i].length<rec[j].length && rec[i].width<rec[j].width){ graph[i][j]=1; } else if(rec[i].length>rec[j].length && rec[i].width>rec[j].width){ graph[j][i]=1; } } } } //记忆化搜索计算动态转移方程（自顶向下）-递归法 int dp(int i){ int &res=d[i];//这里用到这个技巧，对于d[i][j][k][l]等情况实在输入变得太方便了 if(res>0) return res;//>0表示计算过从这个点出发的最长路径了 res=1;//只有一个矩形（例如图中没有出度的点） //从i节点出发，若有从i节点出发的边，就递归搜索 for(int j=0;j<n;j++){ if(1==graph[i][j]){ res=max(res,dp(j)+1);//不断更新从i节点出发的最大长度 }//if }//for return res;//可以看出如果是没有出度的点，就返回1，此时递归返回到上一级（所以递归解决动态规划，递归到终点然后往回一层一层返，在返回的过程中填写结果） } //打印字典序最小的方案 void print_ans(int i){ cout<<i<<" "; for(int j=0;j<n;j++){ if(graph[i][j]==1 && d[j]+1==d[i]){ print_ans(j); break; } } } //打印从i出发的满足最多矩形个数的所有路径 void print_ans2(int i,int cnt){ //path[cnt]=i表示最短路径上的第cnt个点是点i，即矩形i是第cnt个被嵌套的矩形，假设起点是start,就是path[0]=start path[cnt]=i; if(1==d[i]){//如果的d[i]==1，说明已经递归到最后一个矩形了，路径上的所有点都写在path中了，可以打印了 for(int ii=0;ii<=cnt;ii++){ cout<<path[ii]<<" "; } cout<<endl; return; } for(int j=0;j<n;j++){ //下面一定不要少了d[i]==d[j]+1，因为可能j和i相邻，但j不是最短路上的下一个点 //参考图示例，点2和点5之间虽然有边，但不能打印这条路径 //如果把d[i]==d[j]+1去掉，相当于dfs了 if(graph[i][j]==1 && d[i]==d[j]+1){ print_ans2(j,cnt+1); } } } int main() { memset(d,0,sizeof(d)); read(); createGraph(); int ans=1; int mark=0;//标记一下取得最大长度的时候对应的下标 for(int i=0;i<n;i++){ int tmp=dp(i); if(tmp>ans){ ans=tmp;//ans是当前最大长度 mark=i;//i是取得的最大长度的起点，可能不止有一个起点，mark中存放的是第一取得最大长度的点 } } cout<<ans<<endl<<endl; cout<<"字典序最小的路径："; print_ans(mark); cout<<endl; cout<<"按照字典序顺序打印出只满足矩形数最多的路径："<<endl; int all[maxn];//记录所有满足矩形数最多的起点i int cnt=0; for(int i=0;i<n;i++){//遍历所有点，所有最大长度的起点都会找到,cnt是数组下标，记录这是第几个最大长度的起点 if(d[i]==ans){ all[cnt++]=i; } } //打印出共所有满足矩形最多的起点出发的所有路径 for(int i=0;i<cnt;i++){ print_ans2(all[i],0); } return 0; } 转载自https://blog.csdn.net/ccnuacmhdu/article/details/81133637