斜率优化

可以使用滚动数组优化空间

还在努力学习中....

#include <bits/stdc++.h>
#define il inline
#define Max 100005
#define ll long long
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
using namespace std;
namespace lyzqs
{
char In[Max],*ss=In,*tt=In;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
ll f[2][Max],s[Max],ans[305][Max],q[Max],n,k;
il double slope(ll x,ll y,ll nw)
{
    if(s[x]==s[y]) return -1e17;
    return (double)((s[x]*s[x]-f[nw^1][x])-(s[y]*s[y]-f[nw^1][y]))/(1.0*(s[x]-s[y]));
}
void main()
{
    n=read(),k=read();
    for(int i=1;i<=n;i++) s[i]=s[i-1]+read();
    for(int i=1;i<=k;i++)
    {
        ll l=0,r=0;
        int nw=i&1;
        for(int j=1;j<=n;j++)
        {
            while(l<r&&slope(q[l],q[l+1],nw)<=s[j]) l++;
            f[nw][j]=f[nw^1][q[l]]+s[q[l]]*(s[j]-s[q[l]]);
            ans[i][j]=q[l];
            while(l<r&&slope(q[r],j,nw)<=slope(q[r-1],q[r],nw)) r--;
            q[++r]=j;
        }
    }
    printf("%lld\n",f[k&1][n]);
    ll j=n;
    for(int i=k;i>=1;i--)
    {
        j=ans[i][j];
        printf("%lld ",j);
    }
}

}
int main()
{
    lyzqs::main();
}