DP 式子形如
fi=min
移项后得到
f_i + a_i * c_j = f_j
直线方程:
b(f_i) + k(a_i) * x(c_j) = y(f_j)
然后问题变成了二维平面上有很多点,要找到一个点使得在这个点上做斜率为 k 的直线的截距最小。
维护下凸壳(斜率不断增大)即可。