傳送門
把式子展開後發現就是要求：
m∗(∑mi=1sum′[i])−sum[n]2 m ∗ ( ∑ i = 1 m s u m ′ [ i ] ) − s u m [ n ] 2 的最小值。
于是隻需要求：
m∗(∑mi=1sum′[i]) m ∗ ( ∑ i = 1 m s u m ′ [ i ] ) 的最小值。
于是設 f[i][j] f [ i ] [ j ] 表示前i個分了j組的最小值。
顯然有：
f[i][j]=min(f[k][j−1]+(sum[i]−sum[k])2) f [ i ] [ j ] = m i n ( f [ k ] [ j − 1 ] + ( s u m [ i ] − s u m [ k ] ) 2 )
<=>
f[i][j]=min(f[k][j−1]+sum[k]2−2sum[i]∗sum[k])+sum[i]2 f [ i ] [ j ] = m i n ( f [ k ] [ j − 1 ] + s u m [ k ] 2 − 2 s u m [ i ] ∗ s u m [ k ] ) + s u m [ i ] 2
對于兩個決策 k1<k2 k 1 < k 2 且k2比k1更優，有：
f[k1][j−1]+sum[k1]2−2sum[i]∗sum[k1] f [ k 1 ] [ j − 1 ] + s u m [ k 1 ] 2 − 2 s u m [ i ] ∗ s u m [ k 1 ]
>
f[k2][j−1]+sum[k2]2−2sum[i]∗sum[k2] f [ k 2 ] [ j − 1 ] + s u m [ k 2 ] 2 − 2 s u m [ i ] ∗ s u m [ k 2 ]
令 t[k]=f[k][j−1]+sum[k]2 t [ k ] = f [ k ] [ j − 1 ] + s u m [ k ] 2
=>
(t[k1]−t[k2])/(sum[k1]−sum[k2])<2sum[i] ( t [ k 1 ] − t [ k 2 ] ) / ( s u m [ k 1 ] − s u m [ k 2 ] ) < 2 s u m [ i ]
果斷斜率優化。
代碼：
#include<bits/stdc++.h>
#define ll long long
#define N 3005
using namespace std;
inline ll read(){
ll ans=;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<)+(ans<<)+(ch^),ch=getchar();
return ans;
}
int n,m,hd,tl,q[N];
ll sum[N],f[N][N];
inline double slope(int k,int i,int j){return *(f[i][k]+sum[i]*sum[i]-f[j][k]-sum[j]*sum[j])/(sum[i]-sum[j]);}
int main(){
n=read(),m=read();
for(int i=;i<=n;++i)sum[i]=sum[i-]+read(),f[i][]=e18;
for(int j=;j<=m;++j){
hd=tl=,q[1]=;
for(int i=;i<=n;++i){
while(hd<tl&&slope(j-,q[hd+1],q[hd])<*sum[i])++hd;
int k=q[hd];
f[i][j]=f[k][j-]+(sum[i]-sum[k])*(sum[i]-sum[k]);
while(hd<tl&&slope(j-,q[tl],q[tl-1])>slope(j-,i,q[tl]))--tl;
q[++tl]=i;
}
}
cout<<(m*f[n][m]-sum[n]*sum[n]);
return ;
}