分类：DP

2021
07-26

详解DAG上的DP

目录DAG即有向无环图嵌套矩形(不固定起点最长路及其字典序)描述分析解题硬币问题(固定终点的最长路和最短路)描述分析解题小结例题DAG即有向无环图这里举出两经典的DAG模型，嵌套矩形和硬币问题嵌套矩形(不固定起点最长路及其字典序)描述有n个矩形，每个矩形可以用(a,b)来描述，表示长和宽矩形X(a,b)可以嵌套在矩形Y(c,d)中，当且仅当a<c,b<d或者b<c,a<d(旋转90度)例如(1,5)可以嵌套在(6,2)内，但不能嵌套在(3,4)中你的任... 继续阅读 >