查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转斜率优化入门题设$f_i$表示前$i$件玩具的制作费用$$fi=\min{j=1}^{i-1}(f[j]+(i-j-1+s_i-s_j-L)^2)$$显然$\Theta(n^2)$不能满足要求令$a_i=s_i+i,b[i]=s_i+i+L+1$(都只与$i$有关)那么$$fi=\min{j=1}^{i-1}(f_j+(a_i-b_j)^2)\\text{展开得}\f_i=f_j+{a_i}^2-2a_ib_j+{b_j}^2\\text{移项得}\2a_ib_j+f_i-{a_i}^2=f_j+{……