太空飞船（spaceship）

题目描述

21XX年，秋。

小诚是THU（Tomorrow Happy University）航天学院船舶设计系本科四年级的学生。为了顺利毕业，小诚仔细阅读了这几年被引用次数最多的十几篇会议论文，打算在权威理论的指导下设计一艘新型太空飞船。

这将是一艘环形的太空飞船，由N个舱室顺序组成。第i个舱室的设计长度为Li。为了给飞船提供能量，要在飞船上装置K个太空能量吸收器。

根据权威理论，这些吸收器应该尽量均匀地分散在飞船表面。也就是说，小诚要把飞船所有N个舱室划分成K个部分（每个部分包括连续一段舱室），并给每个部分配置一个能量吸收器。设第i个部分舱室的长度之和为si，则要令方差

∑i=1..K(si−s_avg)2∑i=1..K(si−s_avg)2

尽量小。其中s_avg 是K个部分的平均长度。

可是，这个问题对于已经大学四年级的小诚来说太难了。你能否帮助他完成设计呢？

为方便起见，输出方差最小值与K的平方的乘积。

输入

输入文件名为spaceship.in。

第一行，两个整数N，K。

第二行，N个整数L1, L2,⋯, LNL1, L2,⋯, LN，由空格隔开。依次表示每个舱室的长度。

输出

输出文件名为spaceship.out。

输出一行，为一个整数，表示方差最小值与K2K2的乘积。

样例输入

<span style="color:#333333"><span style="color:#333333">【样例输入1】

5 2

4 2 6 1 3

【样例输入2】

5 3

4 2 6 1 3</span></span>

样例输出

<span style="color:#333333"><span style="color:#333333">【样例输出1】

0

【样例输出2】

24</span></span>

提示

【样例解释】

第一组样例。要将飞船分为2段，最优划分方法为[2 6][1 3 4]。

第二组样例。要将飞船分为3段，最优划分方法为[4 2][6] [1 3]。

【数据规模与约定】

本题一共有10个测试点。

对于100%的数据，1≤Li≤1,0001≤Li≤1,000。

来源

BJOI2017一试

化简一下方差的式子，发现等价于要求 $\sum si^2$ 最小。

k=2 双指针维护权值和1/2 的点

k=3 k=2的基础上二分

考虑n<=400的

令f[i][j] 表示前i个点分成j块的最小代价

f[i][j]=f[k][j-1]+(sum[i]-sum[k])^2

展开因为一维j之和上一维有关，滚掉

$f[i]=f[j]+sum[i]^2-2*sum[i]*sum[j]+sum[j]^2$

移过来

$f[i]+2*sum[i]*sum[j]=f[j]+sum[j]^2+sum[i]^2$

sum[i]递增，f[j]+sum[j]*sum[j] 递增

构处凸包就可以斜率优化了

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 600005

#define ll long long

using namespace std;

int n,k,l,r;

ll s[maxn],a[maxn],sum[maxn],f[405];

ll ans=1e18;

struct node{

    ll x,y;

}q[405];

ll val(int a,int b){

    return q[a].y-q[a].x*sum[b]*2;

}

node xl(node a,node b){

    node c;c.x=b.x-a.x;c.y=b.y-a.y;

    return c;

}

ll cr(node a,node b){

    return a.x*b.y-a.y*b.x;

}

void tb(){

    l=1;r=0;

    for(int i=0;i<=n;i++){

        node t=(node){sum[i],f[i]+sum[i]*sum[i]};

        while(r>=2&&cr(xl(q[r-1],q[r]),xl(q[r-1],t))<0)r--;

        q[++r]=t;

    }

}

int main()

{

    cin>>n>>k;

    for(int i=1;i<=n;i++)scanf("%lld",&s[i]),s[i+n]=s[i];

    for(int i=1;i<=2*n;++i)sum[i]=sum[i-1]+s[i];

    if(n<=400){

        for(int d=1;d<=n;d++){

            ll t=s[1];for(int i=1;i<n;i++)s[i]=s[i+1];s[n]=t;

            for(int i=1;i<=n;i++)sum[i]=sum[i-1]+s[i];

            q[1].x=q[1].y=0;l=1,r=1;

            for(int nn=1;nn<=k;nn++){

                //cout<<nn<<endl;

                for(int i=1;i<=n;i++){

                    while(l<r&&val(l,i)>val(l+1,i))l++;

                    f[i]=val(l,i)+sum[i]*sum[i];

                    //cout<<i<<' '<<f[i]<<' '<<l<<' '<<r<<endl;

                }

                tb();

            }

            ans=min(ans,(ll)f[n]*k*k-(ll)(sum[n]*sum[n]*k));

        }

        cout<<ans<<endl;

        return 0;

    }

    if(k==2){

        int j=1;

        for(int i=1;i<=n;i++){

            while((sum[j+1]-sum[i-1])*2<=sum[n]&&j<=i+n-1)j++;

            ll v1=sum[j]-sum[i-1],v2=sum[n]-v1;ans=min(ans,v1*v1+v2*v2);

            v1=sum[j+1]-sum[i-1],v2=sum[n]-v1;ans=min(ans,v1*v1+v2*v2);

        }

    ans=k*(ans*k-(sum[n]*sum[n]));

    cout<<ans<<endl;

    }

    else {

        int j=1;

        for(int i=1;i<=n;i++){

            while((sum[j+1]-sum[i-1])*3<=sum[n]&&j<=n+i-1)j++;

            if(j>n+i-1)break;

            l=j+1;r=n+i-1;// i-j j+1-l l+1-i+n-1

            while(l<r){

                int mid=l+r+1>>1;

                if((sum[mid]-sum[j])*3>sum[n])r=mid-1;

                else l=mid;

            }

            ll v1=sum[j]-sum[i-1],v2=sum[l]-sum[j],v3=sum[n]-v1-v2;ans=min(ans,v1*v1+v2*v2+v3*v3);

            v1=sum[j]-sum[i-1],v2=sum[l-1]-sum[j],v3=sum[n]-v1-v2;ans=min(ans,v1*v1+v2*v2+v3*v3);

            v1=sum[j]-sum[i-1],v2=sum[l+1]-sum[j];v3=sum[n]-v1-v2;ans=min(ans,v1*v1+v2*v2+v3*v3);

        }

        ans=k*(ans*k-(ll)(sum[n]*sum[n]));

        cout<<ans<<endl;

    }

    return 0;

}

巴特西

太空飞船（spaceship）