_pks 'w blog

_pks 'w blog

除了勇气,我什么都不缺。

Higher-level Dynamic Programming——较高级的动态规划 · 区间动规

posted on 2018-02-27 10:03:32 | under 算法学习 |

用这道题引出区间 $DP$ 吧 $qwq$

[蒟蒻的启发式传送门](https://www.luogu.org/problemnew/show/P1063#sub)

$define$ $~$ 区间动规 $~~$ 一维区间动规

一、区间动规的相关

区间动规,说到底也是一位的动态规划,即“线性动态规划”。而最普通的线性动态规划便是一维逻辑关系的动规,即是我们可以由前面推导出来的最优状态推导出当前的最优状态,并且推导的子母顺序大多都是由小到大,或者是某个简单的一维演变次序。

而区间动规的演变次序也是一维的,不过这个一维不同于平常了逻辑上的一维,是由子区间推导出母区间,并具有以下性质( $qwq$ 但这些性质好像对于解题没有什么用处)

并不能通过某种空间时间的次序推演出整体最优值。

(比如不能像背包一样从头到尾枚举物品等)

这个所谓的空间时间推演次序看起来好像很阔怕