斜率优化DP

如果您对DP掌握得很好,可以来尝试着个题单上的题目。

斜率优化的中心思想就是利用一次函数的斜率来优化某些DP转移方程,如果您第一次接触斜率优化的话请戳这里

只有最后一题有一定的思维难度,其他都是模板题。


  1. P2365 - [IOI 2002] 任务安排
  2. P5017 - [NOIP 2018 普及组] 摆渡车
  3. CF311B - Cats Transport
  4. P5785 - [SDOI2012] 任务安排
  5. P3195 - [HNOI2008] 玩具装箱
  6. P2120 - [ZJOI2007] 仓库建设
  7. P3628 - [APIO2010] 特别行动队
  8. P4360 - [CEOI 2004] 锯木厂选址
  9. P3571 - [POI 2014] SUP-Supercomputer