斜率优化DP – Solutions

斜率优化是将方程看起来非常可推的dp从\( O(n^2) \)优化至\( O(n) \)的优秀方法,这种优化是基于决策单调性的……………………

一句话:都是套路。

关于斜率优化的文章很多,而且我数学贼差QAQ(主要是懒),就直接指向一篇本校神犇HenryPigLi的斜率优化DP,虽然他推得有点乱但是还算能看。
然而他的文章还有一个好,就是底下给的题比其他blog都多,于是我觉得应该把solution发出来。

P.S. 这些代码开头都长这样,所以就单独写出来了:


  1. [HNOI2008]玩具装箱
  2. [ZJOI2007]仓库建设
  3. [USACO2008 Mar]土地购买
  4. [Apio2010]特别行动队
  5. 防御准备
  6. [Apio2014]序列分割
  7. 小P的牧场
  8. [SDOI2016]征途

不知不觉我已经成为压行狂魔了QAQ……

发表评论

电子邮件地址不会被公开。 必填项已用*标注

ˆ Back To Top