首页 > 代码库 > DAG模型:嵌套矩形
DAG模型:嵌套矩形
有n个矩形,每个矩形可以用两个整数a,b描述,表示它的长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当 a<c,b<d,或者b<c,a<d(相当于把矩形X旋转90°)。例如(1,5)可以嵌套在(6,2)内,但不能嵌套在 (3,4)内。你的任务是选出尽可能多的矩形排成一行。使得除了最后一个之外,每个矩形都可以嵌套在下一个矩形内。
分析:
矩形之间的"可嵌套"关系是一个典型的二元关系,二元关系可以用图来建模。如果矩形X可以嵌套在矩形Y里,我们就从X到Y连一条有向边。这个 有向图是无环的,因为一个矩形无法直接或间接地嵌套在自己的内部。换句话说,它是一个DAG。这样,我们的任务便是求DAG上的最长路径。
代码:
#include <iostream>
const int maxn = 1000;
typedef struct rectangle
{
int len;
int wid;
};
int Matrix[maxn][maxn];
int length[maxn], n;
rectangle rec[maxn];
void CreateGraph()
{
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(rec[i].len > rec[j].len && rec[i].wid > rec[j].wid)
Matrix[i][j] = 1;
}
}
}
int DynamicPrograming(int i)
{
int& ans = length[i];
if(ans > 0)
return ans;
ans = 1;
for(int j = 0; j < n; ++j)
{
if(Matrix[i][j])
{
int tmp = DynamicPrograming(j);
ans = ans > tmp ? ans : tmp + 1;
}
}
return ans;
}
int _tmain(int argc, _TCHAR* argv[])
{
int N;
std::cin>>N;
while(N-- > 0)
{
int ans=0;
std::cin>>n;
for(int i=0;i<n;i++)
{
int tmp1,tmp2;
std::cin>>tmp1>>tmp2;
rec[i].len=tmp1>tmp2?tmp1:tmp2;
rec[i].wid=tmp1<tmp2?tmp1:tmp2;
}
CreateGraph();
//初始化记忆数组
memset(length,0,sizeof(length));
for(int i=0;i<n;i++)
{
int tmp=DynamicPrograming(i);
ans=ans > tmp ? ans : tmp;
}
std::cout<<ans<<std::endl;
}
return 0;
}
DAG模型:嵌套矩形