slope trick

slope trick，一种比较冷门的 DP 优化技巧，对于一类二维 DP，每一个阶段的 DP 函数都是凸包，可以维护转折点（斜率发生变化的地方）进行转移。

  1. CF13C - Sequence
  2. P4597 - 序列 sequence
  3. P4331 - [BalticOI 2004] Sequence (Day1)
  4. CF713C - Sonya and Problem Without a Legend
  5. CF865D - Buy Low Sell High
  6. P3642 - [APIO2016] 烟花表演
  7. AT_abc217_h - [ABC217H] Snuketoon
  8. CF1534G - A New Beginning