太空飞船（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。
来源
化简一下方差的式子，发现等价于要求最小。
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之和上一维有关，滚掉
移过来
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;
}