查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转设$f(i,j)$表示前$i$个划分成$j$段最少的费用我们设$calc(l,r)$表示$[l,r]$划分成一段的费用$$f(i,j)=\min_{x=1}^i(f(x-1,j-1)+calc(x,i))$$可以发现这个 dp 方程具有决策单调性若$i<i'$,那么$ki\le k{i'}$(决策点)把连续一段拆成两边更优$x^2+y^2\le (x+y)^2(x,y\ge 0)$更巧的是$w(l,r)$可以用类似莫队的方法线性转移这里采用分治的方法实现……