题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3045
题目大意：有n个数，可以把n个数分成若干组，每组不得小于m个数，每组的价值=除了该组最小值以外每个值-最小值之和，求使得所有组的价值之和的最小值。
解题思路：将n个数按从小到大排序，处理前i为前缀和为sum[i],则可得出状态转移方程：dp[i]=min{dp[j]+sum[i]-sum[j+1]-a[j+1]*(i-j-1)}(0<=j<i-m+1)，再用斜率DP优化即可。
注意：一定要判断j是否大于等于m，因为至少m才能算一组奶牛，不然会出错。
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long LL;
const int N=5e5+; int head,tail;
LL sum[N],dp[N],a[N],q[N];; LL getUP(int k,int j){
return dp[j]+a[j+]*(j+)-sum[j+]-dp[k]-a[k+]*(k+)+sum[k+];
} LL getDOWN(int k,int j){
return a[j+]-a[k+];
} //dp[i]=min{dp[j]+sum[i]-sum[j+1]-a[j+1]*(i-j-1)}
LL getDP(int i,int j){
return dp[j]+sum[i]-sum[j+]-a[j+]*(i-j-);
} int main(){
int n,m;
while(~scanf("%d %d",&n,&m)){
memset(dp,0x3f3f3f3f,sizeof(dp));
for(int i=;i<=n;i++){
scanf("%lld",&a[i]);
}
sort(a+,a++n);
for(int i=;i<=n;i++){
sum[i]=sum[i-]+a[i];
}
dp[]=;
head=tail=;
q[tail++]=;
for(int i=;i<=n;i++){
while(head+<tail&&getUP(q[head],q[head+])<=i*getDOWN(q[head],q[head+])){
head++;
}
dp[i]=getDP(i,q[head]);
int j=i-m+;
//注意z这个判断,因为状态转移,也就是分组,至少要保证第一组有m头牛。
if(j<m)
continue;
while(head+<tail&&getUP(q[tail-],j)*getDOWN(q[tail-],q[tail-])<=getUP(q[tail-],q[tail-])*getDOWN(q[tail-],j)){
tail--;
}
q[tail++]=j;
}
printf("%lld\n",dp[n]);
} return ;
}