众所周知，决策单调性分治是为 $f_{i,j} = \min \limits _ {0 \le k \lt i} f_{k,j-1}+w(k+1,i)$ 来做的

void solve(int l, int r, int pl, int pr)
{
	int mid = l + r >> 1; int p = -1;
	for (int i = pl, v; i <= min(pr, mid - 1); i ++ )
		if ((v = f[i][k - 1] + cost(i + 1, mid)) < f[mid][k]) f[mid][k] = v, p = i;
	if (l < mid) solve(l, mid - 1, pl, p); if (r > mid) solve(mid + 1, r, p, pr);
}
\\调用时:
while (k <= m) k ++ , solve(1, n, 0, n - 1); 

但为什么只能这样做？ 而不能将方程写成 $f_{i,j} = \min \limits _ {1 \le k \le i} {f_{k-1,j}+w(k,j)}$，然后决策范围改成 $1 \sim n$ 来做？而这样在 POI1999 地图 中无误，在 IOI2000 邮局中却只能 30 pts。 即改成

void solve(int l, int r, int pl, int pr)
{
	int mid = l + r >> 1; int p = -1;
	for (int i = pl, v; i <= min(pr, mid); i ++ ) //注意范围
		if ((v = f[i - 1][k - 1] + cost(i, mid)) < f[mid][k]) f[mid][k] = v, p = i;
	if (l < mid) solve(l, mid - 1, pl, p); if (r > mid) solve(mid + 1, r, p, pr);
}
\\调用时:
while (k <= m) k ++ , solve(1, n, 1, n);