题面：

【问题描述】

小 Y 喜欢吃坚果,这天他买来了 $n$ 个坚果。每个坚果都需要若干次敲击才能打开。

初始 时,第 $i$ 个坚果需要 $a_i$ 次敲击。然而,他的朋友小 $P$ 趁他不注意,打乱了这些坚果的顺序。小 Y 非常郁闷,于是他想要吃 $m$ 个坚果来平复心情,但是敲击坚果很费体力,所以他并不想过多 敲击。

小 Y 想知道,在最坏情况下,至少需要敲击多少次坚果。小 Y 并不会,于是他把这个任 务交给了你。

【输入格式】

输入数据第一行一个整数 $T$,表示数据组数。接下来是 $T$ 组数据。 每组数据第一行两个整数 $n$ $m$,表示坚果的个数以及小 Y 想要吃的坚果数量。 第二行 襮 个整数 $a_i$ ,表示初始时第 $i$ 个坚果需要敲击的次数。

【输出格式】

对于每组数据,输出一行一个整数,表示至少需要敲击的次数。

RT，部分分中给出了50分的斜率优化，结果调了两个小时，直接裂开

转移方程： $dp{_i,_j}$ $=$ $min$($dp{_k,_{j-1}}$ + $a_i$ $\times$ $(k - i))$ $(i < k ≤ n + 1)$

代码：

  sort(a+1,a+1+n,greater<int>() );
        f[n+1][0]=0;ans=INF;
        for(int i=n-1;i>=0;i--){
        	for(int j=1;j<=m;j++){
        		for(int k=i+1;k<=n;k++){
        			f[i][j]=min(f[i][j],f[k][j-1]+a[k]*(k-i));
        	}
        }
        cout<<f[0][m]<<endl;

double queryk(int k1,int k2,int now){
	return (1.0*f[k1][now]+a[k1]*k1-(1.0*f[k2][now]+a[k2]*k2))/(a[k1]-a[k2]);
}
int main(){
	freopen("nut.in","r",stdin);
	freopen("nut.out","w",stdout);
	int T=read();
	while(T--){
		n=read(),m=read();
        for(int i=1;i<=n;i++)a[i]=read();
        sort(a+1,a+1+n,less<int>() );
        for(int j=1;j<=m;j++){
        	head=tail=0;
        	memset(q,0,sizeof(q));
	        for(int i=n;i>=0;i--){
				while(head<tail&&queryk(q[head],q[head+1],j-1)>i)head++;
				f[i][j]=f[q[head]][j-1]+1LL*a[q[head]]*(q[head]-i);
				while(head<tail&&queryk(q[tail],i,j-1)>=queryk(q[tail],q[tail-1],j-1))tail++;
				q[++tail]=i;
        	}
        }
        cout<<f[0][m]<<endl;
	}
	return 0;
}