前言:
没有前言(快累死了,不想写)。
solution:
设$ f_i $ 为第 $ i $ 句时最小的不协调度。
令 $ w_{i,j}=(s_i+i)-(s_j+j)-(L+1)$。
这里直接写证明了。
视 \(x=w_{i,j}\)。
视 $ c=a_{i+1}+1 $。
忽略 $ w $ 第一维。
\(\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]$。
\(\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]$。
\(\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)$。
\(\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)$。
\(\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)$。
\(\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...