DAG上的动态规划---嵌套矩形(模板题)

时间:2023-03-08 18:05:30
DAG上的动态规划---嵌套矩形(模板题)

一、DAG的介绍

Directed Acyclic Graph,简称DAG,即有向无环图,有向说明有方向,无环表示不能直接或间接的指向自己。

摘录:有向无环图的动态规划是学习动态规划的基础,很多问题都可以转化为DAG上的最长路、最短路或路径计数问题。

通常需要建图,不复杂的也可以当最长上升子序列处理,就不必建图,但都包含运用有向无环图的思想。

二、例题

有n(1 <= n <= 1000)个矩形,长为a,宽为b。矩形X(a,b)可以嵌套在矩形Y(c,d)中,当且仅当a < c,b < d,或者a < d,b < c。求最大的嵌套数。

三、解题思路

矩形X可以嵌套矩形Y,则从X连条边到Y,矩形不能直接或间接的嵌套自己,所以无环。最大的嵌套次数,就是求这个图上的最长路。

四、代码实现

 #include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdbool>
#include<vector>
#include<algorithm>
using namespace std; const int maxn = + ;
struct Node
{
int x, y;
Node(int x, int y) :x(x), y(y) {}
Node() {}
bool operator < (const Node &n)const {
return (x < n.x&& y < n.y) || (x < n.y&& y < n.x);
}
};
vector<Node>vec;
int n;
int d[maxn]; //d[i]表示从节点i出发的最长路的长度
bool G[maxn][maxn];
int cnt = ; //建图
void creatGraph()
{
for (int i = ; i < n; i++)
for (int j = ; j < n; j++)
{
if (vec[i] < vec[j]) G[i][j] = true;
}
} //计算从i出发的最长路径
int dp(int i)
{
int& ans = d[i];
if (ans > ) return ans;
ans = ;
for (int j = ; j < n; j++)
if (G[i][j]) ans = max(ans, dp(j) + );
return ans;
} //解决问题
void slove()
{
creatGraph();
int res = ;
for (int i = ; i < n; i++)
res = max(res, dp(i)); //整体的时间复杂度为O(n^2) printf("Case %d: maximum = %d\n", ++cnt, res);
}
int main()
{
while (scanf("%d", &n) == && n)
{
vec.clear();
memset(d, , sizeof(d));
memset(G, false, sizeof(G));
int x, y;
for (int i = ; i < n; i++)
{
scanf("%d%d", &x, &y);
vec.push_back(Node(x, y));
}
slove();
}
}

当然,这题也可以用最长上升子序列做,可以参考我的前一篇博客。