首先想到的就是sort一下，然后每个集合都在排过序的数组里面取，不重复。
这样就推出公式dp[i][j] = min(dp[k][j-1] + (s[i]-s[k+1])^2)
其中dp[i][j]为在第i位完成j个分组的。
不考虑分组的情况下跟打印文章那题一样。考虑上需要有M个分组，就是两层for循环的dp。
这里往维护的凸包里添加点的时候，要等这一层全部解决之后再一起添进去。保证处理dp第j层时考虑的都是j-1层的情况。
还有就是初始化了。
O(N*M)大概5e7 有点卡，第一次写了个set就TLE了
#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std; const int maxn = 1e4+;
const int maxm = 5e3+; struct Point{
LL x,y;
Point(LL _x=,LL _y=) :x(_x),y(_y){}
bool operator < (const Point &rhs) const
{
if(x == rhs.x) return y < rhs.y;
else return x <rhs.x;
}
LL operator ^(const Point &rhs) const
{
return x*rhs.y - y*rhs.x;
}
Point operator - (const Point &rhs) const
{
return Point(x-rhs.x,y-rhs.y);
}
};
LL func(Point p,LL k)
{
return p.y - k*p.x;
} struct SlopeDP
{
Point ch[maxn];
int head,tail;
void init()
{
tail = ;head = ;
}
void push(Point u)
{
while(head >= && ((ch[head]-ch[head-])^(u-ch[head]) )<=) head--;
ch[++head] = u;
}
Point pop(int k)
{
while(tail < head && func(ch[tail],k) >= func(ch[tail+],k) ) tail++;
return ch[tail];
}
};
int T,N,M;
LL s[maxn],dp[maxn][maxm];
//set <Point> st;
Point save[maxn]; int main()
{
scanf("%d",&T);
int cas = ;
while(T--)
{
memset(dp,,sizeof dp);
scanf("%d%d",&N,&M);
for(int i=;i<=N;i++)
{
scanf("%d",&s[i]);
}
sort(s+,s++N);
SlopeDP H;
H.init();
//st.clear();
int cnt = ;
for(int i=;i<=N;i++)
{
dp[i][] = (s[i] - s[])*(s[i] - s[]);
//st.insert(Point(s[i],s[i]*s[i]+dp[i-1][1]));
save[cnt++] = Point(s[i],s[i]*s[i]+dp[i-][]);
} for(int j=;j<=M;j++)
{
H.init();
for(int i=;i<cnt;i++) H.push(save[i]);
cnt = ;
for(int i=j;i<=N;i++)
{
Point u = H.pop(*s[i]);
dp[i][j] = -*s[i]*u.x + u.y + s[i]*s[i];
//printf("i:%d %d x:%d y:%d k:%d\n",i,dp[i][j],u.x,u.y,-2*s[i]);
//H.push(Point(s[i+1],s[i+1]*s[i+1]+dp[i][j]));
save[cnt++] = Point(s[i+],s[i+]*s[i+]+dp[i][j]);
}
}
printf("Case %d: %lld\n",++cas,dp[N][M]);
}
}