前言：
没有前言（快累死了，不想写）。
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式满足四边形不等式。
Code:
coding...
标签：恶心,不等式,times,ge,right,because,therefore,四边形,left From： https://www.cnblogs.com/lofty2007/p/17741206.html