动态规划训练之十六

https://www.luogu.org/problem/P4072

是P2212(动态规划训练之十五)的提升版

全程抄袭题解

首先化简方差：

这样直接转移就是N×N×N的复杂度，也就是P2212

考虑优化

code:

#include<cstring>
#include<cstdio>
#include<queue>
#define N 3005
#define int long long

int f[N][N];
int que[N];
int sl[N];
int l[N];
int n,m;

int min(int a,int b){return a<b?a:b;}
double slope(int u,int j,int k){return double(f[u][j]-f[u][k]+sl[j]*sl[j]-sl[k]*sl[k])/(double)(sl[j]-sl[k]);}

signed main(){
    scanf("%lld%lld",&n,&m);
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;++i)scanf("%lld",&l[i]);
    for(int i=1;i<=n;++i)sl[i]=sl[i-1]+l[i];
    int h,t;
    f[0][0]=0;
    for(int i=1;i<=n;i++)f[1][i]=sl[i]*sl[i];
    for(int p=2;p<=m;p++){
        h=1,t=0;
        for(int i=1;i<=n;i++) { 
            while(h<t&&slope(p-1,que[h],que[h+1])<2*sl[i])h++;
            int j=que[h];
            f[p][i]=f[p-1][j]+(sl[j]-sl[i])*(sl[j]-sl[i]); 
            while(h<t&&slope(p-1,que[t-1],que[t])>slope(p-1,que[t],i))t--;
            que[++t]=i;
        }
    }
    int ans=m*f[m][n]-sl[n]*sl[n];
    printf("%lld
",ans);
    return 0;
}