关于P5017的斜率优化
  • 板块学术版
  • 楼主AffineRing
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/11/5 19:51
  • 上次更新2023/11/5 08:54:14
查看原帖
关于P5017的斜率优化
399250
AffineRing楼主2020/11/5 19:51

题解中:

fj+sumj=i×cntj+fif_j+sum_j=i\times cnt_j+f_i

(因为fif_i后面一群没影响所以就不打了)

如何看出斜率ii随横坐标cntjcnt_j单调上升?

另外,因为cntjcnt_j的增大则jj肯定增大,所以如果斜率ii单增的话,表明ii越大则决策jj越大,所以是不是有决策单调性?

如果我完全理解错了请各位直接指出,我dp优化刚刚开始学

2020/11/5 19:51
加载中...