最小化村民团体力量之和 - 算法问题

这段文字描述了一个算法问题，问题是关于一个名叫Kars的人对他所在村庄的狭隘思维感到不满和愤怒。他们满足于停留在原地，不努力成为完美的生命形式。作为一位顶尖的发明家，Kars希望改进自己的身体，成为完美的生命形式。不幸的是，村庄中的一些人对他的想法表示怀疑。第i个村民对他有怀疑ai。每个村民个别地害怕Kars，所以他们组成团体以增强力量。\n\n村民团体的力量从l到r被定义为f(l,r)(ai,aj)，其中f(l,r)=|al−al+1|+|al+1−al+2|+…+|ar−1−ar|。这里|x−y|是x−y的绝对值。只有一个村民的团体的力量为0。\n\nKars想要将村民分成恰好k个连续的子团体，使得它们的力量之和最小。具体来说，他必须找到k-1个正整数1≤r1<r2<…<rk-1<n，使得f(1,r1)+f(r1+1,r2)+…+f(rk-1+1,n)最小。帮助Kars找到最小值f(1,r1)+f(r1+1,r2)+…+f(rk-1+1,n)。\n\n输入： \n- 第一行包含一个整数t，表示测试用例的数量。 \n- 每个测试用例的描述如下： \n - 每个测试用例的第一行包含两个整数n和k，表示村民的数量和必须分成的团体数量。 \n - 每个测试用例的第二行包含n个整数a1,a2,…,an，表示每个村民的怀疑程度。\n\n输出： \n- 对于每个测试用例，输出一个整数，表示所有团体力量之和的最小可能值。