诶，这题虽然是决策单调性，但是没人证啊(虽然比较显然)。
那我就来简单证一下叭：
考虑四边形不等式，如果是最小值问题，那大概长这样：
a\leq b<c\leq d
w(a,c)+w(b,d)\le w(a,d)+w(b,c)
那么如果满足这个，就说明其满足最小值时的决策单调性。证明起来很简单，因为 a\to d,b\to c 的转移的值要更大些，所以 a\to c,b\to d 的转移会更优，据此可得 f 有决策单调性。
考虑拿四边形不等式来证明。对于 a\leq b<c\leq d 而言，记 s(a,c) 表示矩阵中左上角为 (a,a) 右下角为 (c,c) 的这么一个矩阵中元素的和，那么
w(a,c)+w(b,d)=\frac{s(a,c)+s(b,d)}{2}
w(a,d)+w(b,c)=\frac{s(a,d)+s(b,c)}{2}
注意到
s(a,d) = s(a,c)+s(b,d)-s(b,c)+s(a,b)+s(c,d)
那么就显然
w(a,c)+w(b,d)\le w(a,d)+w(b,c)
十分满足决策单调性（其实画出图来更显然，就是多了两块矩阵）。
这个东西可以用分治来做。因为每一层决策与本层无关，即 k-1\to k 。于是就可以 solve(l,r,ql,qr) 表示 l\sim r 是从区间 (ql\sim qr) 转移过来的。那么每次取 mid=\frac{l+r}{2}，然后找出 f_{mid} 对应的最优决策所在位置，这样就可以分治了。复杂度 O(nk\log n) 。