DAG 上的 DP
定义
DAG 即 有向无环图,一些实际问题中的二元关系都可使用 DAG 来建模,从而将这些问题转化为 DAG 上的最长(短)路问题。
解释
以这道题为例子,来分析一下 DAG 建模的过程。
有
过程
建立 DAG
由于每个砖块的底面长宽分别严格小于它下方砖块的底面长宽,因此不难将这样一种关系作为建图的依据,而本题也就转化为最长路问题。
也就是说如果砖块
本题的另一个问题在于每个砖块的高有三种选法,怎样建图更合适呢?
不妨将每个砖块拆解为三种堆叠方式,即将一个砖块分解为三个砖块,每一个拆解得到的砖块都选取不同的高。
初始的起点是大地,大地的底面是无穷大的,则大地可达任意砖块,当然我们写程序时不必特意写上无穷大。
假设有两个砖块,三条边分别为
图中蓝色实线框所表示的是一个砖块拆解得到的一组砖块,之所以用
图中黄色虚线框表示的是重复计算部分,可以采用 记忆化搜索 的方法来避免重复计算。
转移
题目要求的是塔的最大高度,已经转化为最长路问题,其起点上文已指出是大地,那么终点呢?显然终点已经自然确定,那就是某砖块上不能再搭别的砖块的时候。
下面我们开始考虑转移方程。
设
其中
贡献者:@WenzelTian@Shuhao@kenlig@Danni@mgt@sshwy@ouuan@TrisolarisHD@Trisolaris@Haoshen@Siger@Ir1d
本页面最近更新:2/3/2023, 12:00:00 AM,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用