#include<stdio.h> #include<string.h> #include<math.h> #include<iostream> #include<algorithm> #include<queue> #include<stack>
#define MAXN 1005
using namespace std;
unsigned long long f[MAXN][MAXN],w[MAXN];
int num[MAXN];
#define FZ(i,p)(f[i-1][p]+num[p+1]*num[p+1])
int i,p;
int que[MAXN],tail,head;
int n,m,j;
bool turnup(int i,int p1,int p2,int p3) //p1>p2>p3
{
unsigned long long y1=FZ(i,p1),x1=num[p1],y2=FZ(i,p2), x2=num[p2], y3=FZ(i,p3), x3=num[p3];
if((x2-x3)*(y1-y2)>(x1-x2)*(y2-y3))return 1;
else return 0;
}int ii,nn;
int main()
{ scanf("%d",&nn);
for(ii=1;ii<=nn;ii++)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
}
sort(num+1,num+n+1);
for(i=1;i<=n;i++)
f[0][i]=(num[i]-num[1])*(num[i]-num[1]);
for(int i=1;i<=m;i++){
head=tail=1;
que[tail++]=0;
for(int j=1;j<=n;j++){
while(head<tail-1&&FZ(i,que[head+1])-FZ(i,que[head])<2*num[j]*(num[que[head+1]]-num[que[head]]))
head++;
int k=que[head];
f[i][j]=f[i-1][k]+(num[j]-num[k+1])*(num[j]-num[k+1]);
while(head<tail-1&&turnup(i,j,que[tail-1],que[tail-2])==0)
tail--;
que[tail++]=j;
}
}
printf("%I64d\n",f[m][n]);
}
}
转载于:https://www.cnblogs.com/Lamboofhome/p/11595519.html
相关资源：垃圾分类数据集及代码
