图的矩阵存储——嵌套矩阵——记忆化搜索搜索

朴灿烈づ我的快乐病毒、 2022-05-08 08:10 111阅读 0赞

转载：[https://www.cnblogs.com/mu-ye/p/7739935.html][https_www.cnblogs.com_mu-ye_p_7739935.html]

## 题意： ##

有n个矩阵，每个矩阵可以用两个整数a、b描述，表示它的长和宽。矩阵X(a，b)可以嵌套在矩形Y(c，d)中，当且仅当a<c，b<d，或者b<c，a<d。输出最多嵌套的矩阵个数。

## 思路： ##

如果矩阵X可以被Y嵌套，则相当于X到Y有一条路径，问题就转化成了在有向无环图中找最长路的问题。

这个问题是动态规划的基础问题。这里用动态规划解决：

设len(i)表示从结点i出发的最长路径长度。状态转移方程为：

len(i) = max\{len(j)+1|(i,j)∈E\}

E是边集。

## 实现： ##

先把n个矩阵处理成一个邻接矩阵。

然后用记忆化搜索的方法实现动态规划方程。

## 输入： ##

10
    1 2
    2 4
    5 8
    6 10
    7 9
    3 1
    5 8
    12 10
    9 7
    2 2

## 输出：   ##

代码：

//Rectangle:长方形 
    //相等的长方形视为放不进去 
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    const int maxlen=100;
    int graph[maxlen][maxlen];//存储图 
    int vmaxlen[maxlen];//存储每个节点的最大长度
    int n;//存储节点数 
    struct node//存储长方形的长和宽 
    {
    	int a,b;
    }; 
    
    int f(int i)//求节点的最大路径长度 
    {
    	if(vmaxlen[i])
    		return vmaxlen[i];
    	int j;
    	vmaxlen[i]=1;//自身为一个长方形 
    	for(j=0;j<n;j++)
    	{
    		if(graph[i][j]) 
    			vmaxlen[i]=max(vmaxlen[i],f(j)+1);//很经典  递归 
    	}
    	return  vmaxlen[i]; 
    } 
    
    void print(int i)
    {
    	cout<<i<<" ";
    	int j;
    	for(j=0;j<n;j++)
    	{
    		if(graph[i][j]&&vmaxlen[i]==vmaxlen[j]+1)//很经典 
    		{
    			print(j);//递推
    			break;
    		} 
    	}
    } 
    
    int main()
    {
    	int i,j;
    	struct node Rect[maxlen]; 
    	memset(graph,0,sizeof(graph));
    	memset(vmaxlen,0,sizeof(vmaxlen));
    	cin>>n;
    	for(i=0;i<n;i++)//输入长方形的长和宽 
    	{
    		cin>>Rect[i].a>>Rect[i].b;
    	} 
    	
    	for(i=0;i<n;i++)//建立图 
    	{
    		for(j=0;j<n;j++)
    		{
    			if((Rect[i].a<Rect[j].a&&Rect[i].b<Rect[j].b)||(Rect[i].a<Rect[j].b&&Rect[i].b<Rect[j].a))
    				graph[i][j]=1;
    		}
    	} 
    	
    	/*for(i=0;i<n;i++)//检测图是否正确建立 
    	{
    		for(j=0;j<n;j++)
    		{
    			cout<<graph[i][j]<<" ";
    		}
    		cout<<endl;
    	}*/ 
    	
    	int tmp;//用来记录那个元素的路径最长
    	int max=-1;//用来记录最长的路径
    	for(i=0;i<n;i++)
    	{
    		if(f(i)>max)
    		{
    			max=f(i);
    			tmp=i;
    		}
    	} 
    	cout<<max<<endl;
    	print(tmp);//打印最长路径
    	
    	return 0; 
    }

[https_www.cnblogs.com_mu-ye_p_7739935.html]: https://www.cnblogs.com/mu-ye/p/7739935.html