这道题原来我已经做过一遍了。。。

本来是斜率优化来着,被我淦成了四边形优化。

重新写一下斜率优化吧。

方法一 斜率优化

记前缀和$s_i$

答案中${s_n}^2$的贡献先不算。

那么方程为

$f_{i,k}=f_{j,k-1}+(s_i-s_j)^2=f_{j,k-1}+{s_i}^2-2s_is_j+{s_j}^2$

$f_{j,k-1}+{s_j}^2=(2*s_i)*s_j+{s_i}^2-f_{i,k}$

发现是一条斜率为$2*s_i$的直线,且$s_i$关于$i$递增而递增。

那么维护一下凸壳即可。

方法二 四边形不等式优化

显然地,$s_{i,j+1}+s_{i+1,j}\ge s_{i,j}+s_{i+1,j+1}$,满足四边形不等式

这里的$s_{i,j}$表示$i$到$j$的区间和。

现在只需要搞定$f_{i,j+1}+f_{i+1,j}\ge f_{i,j}+f_{i+1,j+1}$就好了。

证明$j=1$的情况。

$f_{i,2}+f_{i+1,1}\ge f_{i,1}+f_{i+1,2}$

$f_{i,2}+s_{1,i+1}\ge f_{i+1,2}+s_{1,i}$

设$f_{i,2}$的最优决策为$p(0<p<i)$,即$f_{i,2}=s_{1,p}+s_{p+1,i}$

还有$f_{i+1,2}$的最优决策可能不为$p$,即$f_{i+1,2}\le s_{1,p}+s_{p+1,i+1}$

四边形不等式,
$s_{1,i+1}+s_{p+1,i}\ge s_{1,i}+s_{p+1,i+1}$

有$s_{1,i+1}+s_{1,p}+s_{p+1,i}\ge s_{1,i}+s_{1,p}+s_{p+1,i+1}$

因此
$f_{i,2}+f_{i+1,1}=s_{1,i+1}+s_{1,p}+s_{p+1,i}\ge s_{1,i}+s_{1,p}+s_{p+1,i+1}\ge f_{i,1}+f_{i+1,2}$

之后套证明模板就好了。

这道题奇奇怪怪♂

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=3005,mod=1e9+7,M=1e6;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int a[N],p[N][N];ll sum[N],f[N][N];
int main()
{
    int n,m;qr(n);qr(m);ll s=0;
    for(int i=1;i<=n;i++)qr(a[i]),sum[i]=a[i]+sum[i-1];
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)f[1][i]=sum[i]*sum[i],p[1][i]=1;
    for(int t=2;t<=m;t++)
    {
        p[t][n+1]=n;
        for(int i=n;i;i--)
            for(int k=p[t-1][i];k<=p[t][i+1];k++)
                if(f[t-1][k]+(sum[i]-sum[k])*(sum[i]-sum[k])<f[t][i])
                {
                    f[t][i]=f[t-1][k]+(sum[i]-sum[k])*(sum[i]-sum[k]);
                    p[t][i]=k;
                }
    }
    int t=m,k=n;s=-sum[n]*sum[n];
    while(k)
    {
        int z=p[t][k];if(z==1&&t==1)z=0;
        s+=m*(sum[k]-sum[z])*(sum[k]-sum[z]);
        t--;k=z;
    }
    qw(s);puts("");
    return 0;
}