2013（？）宁波赛羊羊列队，四边形不等式优化 27 分。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
int a[10005],b[10005],f[1005][10005],n,m;
int calc_cost(int l,int r){
	int ans=0;
	for(int i=l+1;i<=r;i++)ans+=a[i]-a[i-1];
	return ans*ans;
}
void bs(int x,int l,int r,int fl,int fr){
	if(l>r)return;
	int mid=(l+r)>>1,res;
	for(int i=fl;i<=fr&&i<=mid;i++){
		int val=f[x-1][i-1]+calc_cost(i,mid);
		if(f[x][mid]>val)f[x][mid]=val,res=i;
	}
	bs(x,l,mid-1,fl,res);
	bs(x,mid+1,r,res,fr);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+1+n);
	memset(f,0x3f3f3f3f,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<=m;i++)bs(i,1,n,1,n);
	cout<<f[m][n];
}

在修建完新路后，小羊们总算可以安心入学了。今年是羊年，新入学的小羊特别多。老师们打算将N只小羊分成M个班级，每个班至少有1只羊。 如何分班成了老师们最头疼的事情，因为开学典礼上，村长就要看到小羊们列队的情况。每个班的小羊都排成一排，站在草场上。村长希望队列中羊的高度尽可能整齐，村长对队列的不整齐度有自己的要求。 例如队列中共有t只羊，高度依次为A1，A2……，At。那么不整齐度为：(|A1-A2|+|A2-A3|+……+|At-1-At|)2。即相邻两只羊高度差之和的平方。 而总体的不整齐度，就是各班不整齐度之和。 现在，请你帮助老师们设计一下，如何分班，如何列队，才能使M个班级的不整齐度之和最小。

30%的数据，1<=N<=10；1<=M<=5； 80%的数据，1<=N<=300；1<=Ai<=1000； 100%的数据，1<=N<=10000,1<=M<=1000，1<=Ai<=1000000，保证M<=N。

懒得修 $\LaTeX$（）