有向无环图上DP
DAG 上的 DPDAG 即 有向无环图,一些实际问题中的二元关系都可使用 DAG 来建模,从而将这些问题转化为 DAG 上的最长(短)路问题。
例题: 巴比伦塔 The Tower of Babylon - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目大意: 有 n(n<=30)
种砖块,已知三条边长,每种都有无穷多个。要求选一些立方体摞成一根尽量高的柱子(每个砖块可以自行选择一条边作为高),使得每个砖块的底面长宽分别严格小于它下方砖块的底面长宽,求塔的最大高度。
思路 不妨将每个砖块拆解为三种堆叠方式,即将一个砖块分解为三个砖块,每一个拆解得到的砖块都选取不同的高。 也就是说如果砖块 i
能放在砖块 j
上,那么 i
和 j
之间存在一条边 (i,j)
,且边权就是砖块 j
所选取的高。一次建立有向无环图 堆叠方式有可能是 ABC
也有可能是 DBC
,为了防止重复所搜,采用记忆化搜索
代码