自认为有一种更加清晰的状态设计
查看原帖
自认为有一种更加清晰的状态设计
350880
MaxBlazeResFire楼主2023/9/22 17:41

记 fi,j,kf_{i,j,k} 表示距离 ii 最近的建了伐木场的祖先为 jj,钦定 ii 不建造伐木场,ii 子树内共建了 kk 个伐木场时,ii 子树内部不包括 ii 的所有点生产的木材产生的最小代价(要算到运到 jj 为止)。

记 gi,kg_{i,k} 表示钦定 ii 建造伐木场,ii 子树内共建了 kk 个伐木场时,所有 ii 子树内生产的木材产生的最小代价(这里 ii 子树内所有生产的木材都能在 ii 子树内部消化掉)。

记 hi,j,kh_{i,j,k} 表示距离 ii 最近的建了伐木场的祖先为 jj,ii 子树内共建了 kk 个伐木场时,ii 子树内产生的所有木材在所有情况下可能造成的最小代价,不考虑其它因素。

对于 gg,要求第二维大于等于 11。

感觉这个东西理解起来更简单一些,下标和转移方向之类的都没有很绕的地方。

复杂度 O(n4)O(n^4)。

2023/9/22 17:41
加载中...