题目描述

有n名学生参加军训，军训的一大重要内容就是走队列，而一个队列的不整齐程度是该队中最高的学生的身高与最矮的学生的身高差值的平方。
现在要将 n名参加军训的学生分成 k个队列，每个队列的人数可以是任意非负整数。
在安排队列时希望所有队列的不整齐度之和尽量小，请问不整齐度之和最小可以是多少？

样例

3 2
170 180 168

算法1

(斜率优化dp)

本题数据范围好像不大，但是最近刚在写了几题斜率优化，发现这个好像是个模板题，就拿来水一水
首先，我们要把数据进行贪心排序，因为这样我们可以最好的控制最大值最小值之间的距离
然后我们发现本题的数据都是正数，所以本题既可以删队头也可以删队尾
y总在提高课上详细的描述了线性规划的做法，那我来讲一讲代数法的应用
代数法其实更好理解：
设计状态 f[i][x]为前i个分为j队的最小值
所以 f[i][x]=min(f[j][x-1]+(a[i]-a[j+1])*(a[i]-a[j+1]))
我们看到费用的表示有i项和j项的乘积，自然想到斜率优化
假设k<j,并且f[k][x-1]+(a[i]-a[k+1])*(a[i]-a[k+1])>f[j][x-1]+(a[i]-a[j+1])*(a[i]-a[j+1])
我们进行移项得到
f[j][x-1]+a[j+1]*a[j+1]-(f[k][x-1]+a[k+1]*a[k+1])/(a[j+1]-a[k+1])<=2*a[i]
我们发现因为a[i]在不断递增，所以假如这个式子现在成立，那么以后一定成立，因此k项可以删除
我们继续考虑队尾的凸包维护
定义g[k,j]为j和k项之间的斜率且k<j;
所以我们可以看出以下两点：我们令g[k,j]=(yj-yk)/(xj-xk)
我们需要证明当g[k,j]>g[j,i]的时候，j点永远没用，这里的k,j分别是在单调队列中的倒数两个数
如果 k<j<i   而且 g[k,j]>g[j,i] 那么 j 是可以淘汰的。
假设  g[j,i]<=2*a[i]就是i比j优，那么j没有存在的价值
相反如果 g[j,i]>=2*a[i] 那么同样有 g[k,j]>=2*a[i]  那么 k比 j优 那么  j 是可以淘汰的

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int N=1100;
const int inf=0x3f3f3f3f;
int a[N];
int q[N];
int s[N];
int f[N][N];
int getup(int j,int i,int x){
    return f[i][x-1]+a[i+1]*a[i+1]-(f[j][x-1]+a[j+1]*a[j+1]);
}
int getdown(int j,int i){
    return a[i+1]-a[j+1];
}
int main(){
    int n;
    int k;
    int i;
    cin>>n>>k;
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+1+n);
    memset(f,0x3f,sizeof f);
    if(n<=k){
        cout<<0<<endl;
        return 0;
    }
    f[0][0]=0;
    int tt=0;
    int hh=0;
    int x; 
    for(x=1;x<=k;x++){
        tt=0;
        hh=0;
        q[0]=x-1;//注意这里
        for(i=x;i<=n;i++){
            while(hh+1<=tt&&getup(q[hh],q[hh+1],x)<=2*a[i]*getdown(q[hh],q[hh+1]))
            hh++;
            f[i][x]=f[q[hh]][x-1]+(a[i]-a[q[hh]+1])*(a[i]-a[q[hh]+1]);
            while(hh+1<=tt&&getup(q[tt-1],q[tt],x)*getdown(q[tt],i)>=getdown(q[tt-1],q[tt])*getup(q[tt],i,x))
            tt--;
            q[++tt]=i; 
        }
    }
    cout<<f[n][k]<<endl; 
}