前提条件

对于\(a\le b\le c\le d\)，有\(f[a][c]+f[b][d]\le f[a][d]+f[b][c]\)，

证明内容

对于\(l,r,opt\in(l,r)\)，
若已知：\(\forall opt'\neq opt,opt'\in(l,r),f[l][opt]+f[opt+1][r]\le f[l][opt']+f[opt'+1][r]\)，记作\(1\)式。
求证：\(\forall opt'\in(l,opt),f[l][opt]+f[opt+1][r+1]\le f[l][opt']+f[opt'+1][r+1]\)

证明过程

证：
代入\(a=opt'+1,b=opt+1,c=r,d=r+1\)至前提条件，
得到\(f[opt'+1][r]+f[opt+1][r+1]\le f[opt'+1][r+1]+f[opt+1][r]\)，记作\(2\)式。
通过\(1\)式加\(2\)式，并消去整理，得证