zcmimi's blog

查看原题

点击跳转

根据平方和公式可以发现分越多段越好

而进一步又可以发现最后一段的总和越小越好

以下是88分代码(高精什么的懒得写了):

#include<bits/stdc++.h>
const int N=4e7;
int n,typ,a[N],q[N];
long long s[N],f[N],g[N];
int main(){
    scanf("%d%d",&n,&typ);
    if(!typ)
        for(int i=1;i<=n;++i)scanf("%d",a+i),s[i]=s[i-1]+a[i];
    else{

    }
    int h=0,t=0;
    for(int i=1;i<=n;++i){
        while(h<t&&f[q[h+1]]<=s[i]-s[q[h+1]])++h;// 在满足递增的前提下,越多分配给前面,后面就可以越小
        f[i]=s[i]-s[q[h]];g[i]=g[q[h]]+f[i]*f[i];
        while(h<t&&f[q[t]]-f[i]>=s[i]-s[q[t]])--t;// 维护单调队列
        q[++t]=i;
    }
    printf("%lld\n",g[n]);
}
LG 5665 划分
comment评论
Search
search