実線の長さが入っている．点線は考慮しない．dp(i,j)を[i,j]での答えとすると， v = dp1(i,r)+dp2(r,j)として， dp1(i,j) = v+x[j-1]-x[i] dp2(i,j) = v+y[i]-y[j-1] dp(i,j) = v+x[j-1]+x[i]+y[i]-y[j-1] となるrがある．dp1(i,r)+dp2(r,j)が暫定最適値より…

多項式を区分的線形関数で近似する問題．お気に入りというわけではないが，ちょっと面白かった．便宜上，求める関数を [tex:g(x)=\begin{cases}a_1(x-c)+b & (xc) \end{cases}] とする． をどうにかしたい．ポイントは，2つ． bを決めるとa1とa2は独立に求ま…