这道题看上去和干草堆很像啊$\cdots$


仔细观察题意可得知,

一定要分多段,$(a+b)^2>a^2+b^2$

这个结论不难得出。

这样可以得到一个$n^2$的做法。

for(int i=1;i<=n;i++)
{
    for(int j=i-1;j;j--)
        if(s[i]-s[j]>=g[j]&&f[j]+(s[i]-s[j])*(s[i]-s[j])<f[i])
        {
            f[i]=f[j]+(s[i]-s[j])*(s[i]-s[j]);
            g[i]=s[i]-s[j];
            break;
        }        
}

这个做法就不解释了。

尝试$88pts$.

既然要分多段,那么最后一段一定要尽可能小(这个条件的转化要看干草堆)。

那么貌似会有一个方程(前缀和$s$)

$f_i=\min\limits_{j<i,f_j\le s_i-s_j}s_i-s_j$

搞一搞发现没有单调性(因为本来就是单调的233,也许可能我搞错了。)

那么现在怎么办呢?

试一下后缀和,

$f_i=\min\limits_{j<i,f_j\le s_{j+1}-s_{i+1}}s_{j+1}-s_{i+1}$

$f_j-s_{j+1}\le -s_{i+1}$,$-s_{i+1}$单调递增。

就可以进行单调队列优化方程了。