slope trick

slope trick，一种比较冷门的 DP 优化技巧，对于一类二维 DP，每一个阶段的 DP 函数都是凸包，可以维护转折点（斜率发生变化的地方）进行转移。