题目链接
一道可爱的区间DP。。。
题目中有一个很容易证明,又很不容易被注意到,但是又很重要的点:最优解的每一步中已经修好的点恰好是连续的。
那怎么证明呢?很简单,去维修不在当前区间处的点时一定会经过一些点,反正维修不需要时间,那我们经过它们时何不“顺便”修好它们?早晚都是要修的,那还不如早点修完避免它们的花费一直上升。