诗人小G （恶心的四边形不等式证明）-526互联

前言：

没有前言（快累死了，不想写）。

solution：

题目传送门

设$ f_i $ 为第 $ i $ 句时最小的不协调度。

\[f_i = f_j + \left |s_i-s_j+i-j-1-L\right |^P \]

\[f_i=f_j+\left |s_i+i-(s_j+j)-(L+1)\right |^P \]

令 $ w_{i,j}=(s_i+i)-(s_j+j)-(L+1)$。

\[f_i=f_j+\left | w_{i,j} \right|^P \]

这里直接写证明了。

\[\begin{cases}w(i+1,j)+w(i,j+1)\ge w(i,j)+w(i+1,j+1)&j<i\end{cases} \]

\[\begin{cases}w(i,j+1)-w(i+1,j+1)\ge w(i,j)-w(i+1,j)&j<i\end{cases} \]

\[\left| w_{i,j+1}\right|^P-\left|w_{i,j+1}+a_{i+1}+1\right|^P\ge \left|w_{i,j}\right|^P-\left|w_{i,j}+a_{i+1}+1\right|^P \]

\[w_{i,j+1}=(s_i+i)-(s_{j+1}+j+1)-(L+1) \]

\[w_{i,j+1}=(s_i+i)-(s_j+a_{j+1}+j+1)-(L+1) \]

\[w_{i,j+1}=(s_i+i)-(s_j+j)-(L+1)-a_{j+1}-1 \]

\[w_{i,j+1}=w_{i,j}-a_{j+1}-1 \]

\[\left|w_{i,j}-a_{j+1}-1\right|^P-\left|w_{i,j}-a_{j+1}-1+a_{i+1}+1\right|^P\ge\left|w_{i,j}\right|^P-\left|w_{i,j}+a_{i+1}+1\right|^P \]

视 $x=w_{i,j}$。

\[\left|x-a_{j+1}-1\right|^P-\left|x-a_{j+1}+a_{i+1}\right|^P\ge\left|x\right|^P-\left|x+a_{i+1}+1\right|^P \]

视 $ c=a_{i+1}+1 $。

\[\left|x-a_{j+1}-1\right|^P-\left|x-a_{j+1}-1+c\right|^P\ge\left|x\right|^P-\left|x+c\right|^P \]

忽略 $ w $ 第一维。

\[\left|x_{j+1}\right|^P-\left|x_{j+1}+c\right|^P\ge\left|x_j\right|^P-\left|x_j+c\right|^P \]

$\because x_{j+1} \le x_j$

$\therefore $ 问题转为证明函数 $f(x)=\left|x\right|^P-\left|x+c\right|^P$ 单调递减。

$1:P$ 为奇数且 $ x \in \left(-c , 0\right]$。

\[f'(x)=-P\times x^{P-1}-P\times \left(x+c\right)^{P-1} \]

$\because P$ 为奇数，$\therefore P-1$ 为偶数。$\therefore x^{P-1}\ge0 \,\&\,\left(x+c\right)^{P-1}\ge0$。

$\therefore f'(x) \le 0$。

$\therefore $ 原函数单调递减。

$2:P$ 为奇数且 $ x\in\left(-\infty,-c\right]$。

\[f'(x)=-P\times x^{P-1}+P\times \left(x+c\right)^{P-1} \]

$\because P$ 为奇数，$\therefore P-1$ 为偶数。$\therefore x^{P-1}\ge0 \,\&\,\left(x+c\right)^{P-1}\ge0$。

$\because x < 0 \quad \therefore x^{P-1} \ge (x+c)^{P-1}$。

$\therefore $ 原函数单调递减。

$3:P$ 为奇数且 $ x\in\left(0,\infty\right)$。

\[f'(x)=P\times x^{P-1}-P\times \left(x+c\right)^{P-1} \]

$\because P$ 为奇数，$\therefore P-1$ 为偶数。$\therefore x^{P-1}\ge0 \,\&\,\left(x+c\right)^{P-1}\ge0$。

$\because c > 0 \quad \therefore x^{P-1} < \left(x+c\right)^{P-1}$

$\therefore f'(x) < 0$。

$\therefore $ 原函数单调递减。

$4:P$ 为偶数且 $ x \in \left(-\infty,0\right)$。

\[f(x)=x^P - \left(x+c\right)^P \]

\[f'(x)=P \times x^{P-1}-P \times \left(x+c\right)^{P-1} \]

$\because x < 0 \quad \therefore P \times x^{P-1} < 0 \quad -P \times (x+c)^{P-1}>0$

$\because x < 0 \quad \therefore x^{P-1}>(x+c)^{P-1}$

$\therefore f'(x)<0$

$\therefore $ 原函数单调递减。

$5: P$ 为偶数且$ x \in \left[0,\infty\right)$。

\[f(x)=x^P - \left(x+c\right)^P \]

\[f'(x)=P \times x^{P-1}-P \times \left(x+c\right)^{P-1} \]

$\because x \ge 0 ,c>0\quad \therefore x^{P-1} < (x+c)^{P-1}$

$\therefore f'(x) < 0 $

$\therefore $ 原函数单调递减。

综上，原函数在 $ P>0,c>0 $ 的条件下单调递减。

所以原dp式满足四边形不等式。

coding...