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();

     }

 }

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

巴特西

DAG上的动态规划---嵌套矩形（模板题）

最新文章

热门文章