Solution

通过观察可得，如果已经规定了分割方案，则分割顺序不影响分割得到的结果。

考虑被分成的数个块。当一个块与另一个块被分割开来，整个式子中就出现两个块相乘的项，并且只会出现一次。

所以假设被分成了四个块 $s_1,s_2,s_3,s_4$，那么结果就是 $s_1s_2+s_1s_3+s_1s_4+s_2s_3+s_2s_4+s_3s_4$。

然后就可以分 $k$ 层斜率优化了。

注意细节，一是 $x$ 不一定是严格递增的，二是一定至少要分割 $k$ 次。

不建议在 luogu 测，luogu 数据太水了。

Code

// Code by ajcxsu
// Problem: sequence div

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
typedef long long ll;
ll f[2][N], *tf=f[0], *lf=f[1], x[N], y[N], s[N];
int pre[201][N];
int qu[N], h, t;

int main() {
    int n, k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>s[i], s[i]+=s[i-1];
    ll K; int j; 
    for(int nk=1;nk<=k;nk++) {
        swap(tf, lf);
        h=t=0;
        for(int i=nk;i<=n;i++) {
            K=-s[i];
            while(t-h>1 && y[qu[h+1]]-y[qu[h]]>(x[qu[h+1]]-x[qu[h]])*K) h++;
            if(t!=h) j=qu[h], tf[i]=y[j]-K*x[j], pre[nk][i]=j;
            x[i]=s[i], y[i]=lf[i]-s[i]*s[i];
            while((t-h>1 && (y[qu[t-1]]-y[qu[t-2]])*(x[i]-x[qu[t-1]])<(y[i]-y[qu[t-1]])*(x[qu[t-1]]-x[qu[t-2]]))
                        || (t-h && x[i]==x[qu[t-1]] && y[i]>=y[qu[t-1]])) t--;
            qu[t++]=i;
        }
    }
    cout<<tf[n]<<endl;
    for(int i=k, na=pre[k][n];i>=1;i--, na=pre[i][na]) cout<<na<<' ';
    cout<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-uoj-104.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆