求助斜率优化的一个小问题
查看原帖
求助斜率优化的一个小问题
191281
Jr_Zlw楼主2021/4/23 21:14

比如这题,将前面的的状态转移成点以后是

P(sum[j],a×sum[j]2+b×sum[j]+dp[j])P(sum[j],a\times sum[j]^2+b\times sum[j]+dp[j])

横坐标是是单增的,但纵坐标貌似没啥规律。

但这题斜率恒为负数,所以找斜率 >0>0 的上凸包就行。

  1. 求助如果斜率不是恒为负数的话怎么处理?

  2. 以及如果斜率不是单增或单减的话可以搞吗?

  3. 如果斜率的变化呈某一种规律(如抛物线)能搞吗?

求助,谢谢大佬们!

2021/4/23 21:14
加载中...