# 浅谈平行四边形优化（包含正确性证明）

## 1.概述

$$m(i,j) =\begin{cases} \displaystyle\min_{i<k\le j}{m(i,k-1)+m(k,j)+w(i,j)} &\text{if } i<j \ 0 &\text{if } i=j \ \infty &\text{if } i>j \end{cases}$$

$w(i’,j’)\le w(i,j’)$ (1.1)

$w(i,j)+w(i’,j’)\le w(i’,j)+w(i,j’)$ (1.2)

$m_k(i,j)=m(i,k-1)+m(k,j)+w(i,j)(i\lt k\le j)$

$$s(i,j)=\begin{cases} \displaystyle\max_{i<k \le j}{k|m(i,j)=m_k(i,j)} &\text{if } i<j \ 0 &\text{if } i \ge j \end{cases}$$

## 2.结论，操作与时间复杂度

$m(i,j)=\begin{cases} \displaystyle\min_{s(i,j-1)\le k \le s(i+1,j)}{m_k(i,j)} &\text{if } j>i+1 \ m(i,i)+m(j,j)+w(i,j) &\text{if } j=i+1 \ 0 &\text{if } j=i \ \infty &\text{if } j<i \end{cases}$

$$s(i,j) = \begin{cases} \displaystyle\max_{s(i,j-1) \le k \le s(i+1,j)}{k|m(i,j)=m_k(i,j)} &\text{if } j>i+1 \ j &\text{if } j=i+1 \ 0 &\text{if } j<i+1 \end{cases}$$

$$T(n)=\displaystyle \sum_{len=3}^{n} \displaystyle \sum_{i=1}^{n-len+1}[s(i+1,i+len-1)-s(i,i+len-2)+1]+n-1$$
$$=\displaystyle\sum_{len=3}^{n}[s(n-len+2,n)-s(1,len-1)+n-len+1]+n-1$$
$$\le \displaystyle\sum_{len=3}^{n}(n+n)+n-1$$
$$=O(n^2)$$

## 3.平行四边形优化正确性证明

【性质1】对于任意$i\le i’ \le j \le j’$，有$m(i,j)+m(i’,j’) \le m(i’,j)+m(i,j’)$

$m(k,j)+m(j,j’)\le m(k,j’)$     (2.1)

$m(i,j)+m(j,j’) \le [m(i,k-1)+m(k,j)+w(i,j)]+m(j,j’)$
$\phantom{1000} \le m(i,k-1)+m(k,j)+w(i,j’)+m(j,j’)$  （由式(1.1)得）
$\phantom{1000} \le m(i,k-1)+m(k,j’)+w(i,j’)$（由式(2.1)得）
$\phantom{1000} \le m(i,j’)$

$m(z,j)+m(y,j’)\le m(y,j)+m(z,j’)$ (2.2)

$m(i,j)+m(i’,j’)\le w(i,j)+m(i,z-1)+m(z,j)+w(i’,j’)+m(i’,y-1)+m(y,j’)$
$\le w(i’,j)+w(i,j’)+m(i,z-1)+m(i’,y-1)+m(y,j)+m(z,j’)$（由式(1.2)(2.2)得）
$\le m(i,j’)+m(i’,j)$

【性质2】对于任意$j>i+1$，有$s(i,j-1)\le s(i,j) \le s(i+1,j)$

$m(i,j) =\begin{cases} \displaystyle\min_{i<k\le j}{m(i,k-1)+m(k,j)+w(i,j)} &\text{if } i<j \ 0 &\text{if } i=j \ \infty &\text{if } i>j \end{cases} \$

$m_k(i,j)=m(i,k-1)+m(k,j)+w(i,j)(i<k\le j)$

$s(i,j)=\begin{cases} \displaystyle\max_{i<k \le j}{k|m(i,j)=m_k(i,j)} &\text{if } i<j \ 0 &\text{if } i \ge j \end{cases}$

$w(i’,j’)\le w(i,j’)$ (1.1)

$w(i,j)+w(i’,j’)\le w(i’,j)+w(i,j’)$ (1.2)

$m(i,j)+m(i’,j’) \le m(i’,j)+m(i,j’)$(性质1)

$m_k(i,j)\ge m_{s(i,j)}(i,j)(k\le s(i,j))$ (3.1)

$m_k(i,j)>m_{s(i,j)}(i,j)(k>s(i,j))$(3.2)

$m(k,j-1)+m(s(i,j-1),j)\le m(s(i,j-1),j-1)+m(k,j)$

$m_k(i,j-1)+m_{s(i,j-1)}(i,j)\le m_{s(i,j-1)}(i,j-1)+m_k(i,j)$

$m(i+1,k-1)+m(i,s(i+1,j)-1)\le m(i,k-1)+m(i+1,s(i+1,j)-1)$

$m_k(i+1,j)+m_{s(i+1,j)}(i,j)\le m_k(i,j)+m_{s(i+1,j)}(i+1,j)$

$m(i,j)=\begin{cases} \displaystyle\min_{s(i,j-1)\le k \le s(i+1,j)}{m_k(i,j)} &\text{if } j>i+1 \ m(i,i)+m(j,j)+w(i,j) &\text{if } j=i+1 \ 0 &\text{if } j=i \ \infty &\text{if } j<i \end{cases}$