诗人小G

id: poetG

证明:

证明val(i,j)val(i,j)具有

  1. 四边形不等式
  2. 单调性

证明DP公式具有决策单调性

j<ij < i,若ii对于xx来说,比jj优,则对于∀y>x\forall y >x,ii都比jj优.

证明在P数组是f[i],具有二分单调性.

1 1 1 1 2 2 2 2  3 3 3 3

即

  1. j<ij<i, 若i对2优,则对于y>2,i都比j优. 后半部分都成立

  2. j<ij<i, 若i对2不优,则对于y<2,i都比j都不优. 前半部分都成立

证明 按如上的操作: 不漏

证明: i不会覆盖真正的最优分割点.