又来水博客了
[SDOI2016]征途
推一下柿子就会发现，我们要求最小值的部分是将整个序列分为来m段，然后每段和的平方相加最小。
\(f[i][j]=f[k][j-1]+(s[i]-s[k])^2\),然后用滚动数组优化一下。
\(g[i]=f[k]+s[i]^2-2s[i]s[k]+s[k]^2\)
\(f[k]+s[k]^2=g[i]-s[i]^2+2s[i]s[k]\)
将决策看作(\(2s[k]\),\(f[k]+s[k]^2\))即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
using namespace std;
typedef long long ll;
const int N=3005;
ll f[N],g[N],s[N],z,ans;
int h,t,q[N],n,m;
ll Y(int x){
return f[x]+s[x]*s[x];
}
ll X(int x){
return 2*s[x];
}
ll down(int a,int b){
return X(a)-X(b);
}
ll up(int a,int b){
return Y(a)-Y(b);
}
ll sqr(ll x){
return x*x;
}
int main(){
// freopen("data.in","r",stdin);
scanf("%d %d",&n,&m);
fo(i,1,n) {
scanf("%lld",&z);
s[i]=s[i-1]+z;
}
memset(f,0x3f,sizeof(f));
f[0]=0;
fo(j,1,m){
h=t=1;
memset(q,0,sizeof(q));
fo(i,1,n) {
while (h<t && up(q[h+1],q[h]) <= s[i]*down(q[h+1],q[h]) ) h++;
g[i]=f[q[h]]+sqr(s[i]-s[q[h]]);
while (h<t && up(i,q[t])*down(q[t],q[t-1]) <=down(i,q[t])*up(q[t],q[t-1]) ) t--;
q[++t]=i;
}
fo(i,1,n) f[i]=g[i];
}
ans=m*f[n]-sqr(s[n]);
printf("%lld\n",ans);
return 0;
}