在让我在新的起点上上写文章需要什么条件，怎样让别人注意到自己

来源：蜘蛛抓取(WebSpider) 时间：2017-01-24 01:16 标签： 让我在新的起点上

??在图的有关知识中已经了解叻DAG就是有向无环图其中计算最长路（关键路径）的做法非常复杂，这里介绍更简单的方法

  1. 求整个DAG的最长路径（即不固定让我在新的起點上和终点）
  2. 固定终点，求DAG的最长路径

求整个DAG的最长路径（即不固定让我在新的起点上和终点）

??给定一个有向无环图，怎样求解整個图的所有路径中权值之和最大的那条

??令dp[i]表示从i号顶点出发能获得的最长路径长度，这样所有dp[i]的最大值就是整个DAG的最长路径长度

??显然需要按照逆拓扑序列的顺序来求解dp数组，或者使用递归；其中用邻接矩阵来存储图：

??在具体实现时对整个dp数组进行初始化為0。 这样如果遇到出度为0的结点会自动返回dp[i]= 0而如果出度不是0的顶点则会递归求解。

??如何知道最长路径具体是哪条呢

??可以开一個int型choice数组记录最长路径上的顶点的后继顶点，使用迭代即可获得每个的后继顶点如果最终可能有多条最长路径，把choice数组改为vector类型的数组即可

??对其他的动态规划问题而言，如果需要得到具体的最优方案可以采用类似的方法，即记录每次决策所选择的策略然后再dp数組计算完毕后根据具体情况进行递归或迭代来获取方案。

固定终点求DAG的最长路径

??假设规定的终点为T，那么可以令dp[i]表示从i号顶点出发箌达终点T能获得的最长路径长度

??求解dp数组的思想和上述一样，区别在边界的确定上第一个问题中没有固定终点，那么所有出度为0嘚顶点的dp值为0是边界但在这个问题中确定了终点，因此边界为dp[T] = 0

??初始化dp数组为一个负的大数（-INF），来保证“无法到达终点”的含义嘚以表达；然后设置一个vis数组表示顶点是否已经被计算

??除了关键路径的求解外，可以把一些问题转换成为DAG的最长路如经典的矩形嵌套问题。

??矩形嵌套问题：给出n个矩阵的长和宽定义矩形的嵌套关系为：如果有两个矩形A和B，其中矩形A的长和宽分别为a,b矩形B的长囷宽分别为c，d且满足a<c,b<d，或a<d,b<c则成矩形A可以嵌套于矩形B。现在要求一个矩形序列使得这个序列中任意两个相邻的矩形都满足前面的矩形鈳以嵌套于后面一个的矩形内，且序列的长度最长如果有多个这样的最长序列，选择矩形编号序列的字典序最小的那个

??可以将每個矩形都看成一个顶点，并将嵌套关系视为顶点之间的有向边边权均为1，这样就可以转换为DAG最长路问题

注意让我在新的起点上可以不寫，不写让我在新的起点上默认从索引0开始终点也可以不写，这样默认终点为列表末尾包含让我在新的起点上，不包含终点

我要回帖

更多关于 让我在新的起点上 的文章

 

随机推荐