Monthly Archives

6 Articles

信息学奥林匹克竞赛

NOI 复习专题 – DP

Posted by kal0rona on

斜率优化

斜率优化其实不是很难,可以理解为在平面上的一些点作为决策点,而你现在有一条斜率为 \(k\) 的直线,你需要使其经过一个合适的点,使得这条线的截距最大/最小化。这个显然可以使这些点组成一个上/下凸包、然后二分找到斜率相近的那条线段进行转移。