草稿纸

\begin{align}\frac{(\sum x_i \times \overline{x}+\overline{x})^2}{\overline{x}^2}&=\frac{(\sum x \times \sum x+\sum x )^2}{(\sum x)^2}\\&=\frac{(s^2+s)^2}{s^2}\\&=\frac{(s^4+2s^3+s^2)}{s^2}\\&=s^2+2s+1\\&=(s+1)^2\end{align}

设

s_i=\sum_{j=1}^ia_i

，设决策点

j_1<j_2

，

j_1

比

j_2

不优，则

\begin{align}(s_i-s_{j_1}+1)^2&>(s_i-2_{j_2}+1)^2\\s_i^2-2s_is_{j_1}+s_i+s_{j_1}^2-2s_{j_1}+1&>s_i^2-2s_is_{j_2}+s_i+s_{j_{2}}^2-2s_{j_2}+1\\-2s_is_{j_{1}}+s_{j_{1}}^2-2s_{j_{1}}&>-2s_is_{j_{2}}+s_{j_{2}}^2-2s_{j_{2}}\end{align}

设

X(i)=2s_i

，

Y(i)=s_i^2-2s_i

则

\begin{align}-s_iX(j_1)+Y(j_1)&>-s_iX(j_2)+Y(j_2)\\Y(j_1)-Y(j_2)&>s_i(X(j_1)-X(j_2))\end{align}

因为

j_1 < j_2

，所以

X(j_1)<X(j_2)

\begin{align}s_i &> \frac{Y(j_1)-Y(j_2)}{X(j_1)-X(j_2)}\\s_i &> \frac{Y(j_2)-Y(j_1)}{X(j_2)-X(j_1)}\end{align}

于是斜优 dp 部分完结撒花。

文章操作