题目地址：http://vjudge.net/problem/UVALive-4731
如何 分组 问题
以往遇到的这种题目，需要分组的，都是二进制枚举子集，暴力求解的，但这里数据量达100，所以根本不可能
这个应该是DP,DP的状态压缩也不可能，都不知道怎么表示状态，那么只有贪心了 ，贪心也没有思路..
看题解：先从大到小排序，那么就是连续的数字中分组了，那么就可以DP了
d[i][j] 表示i组以j结尾最小的期望
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
const int maxn=100+5,INF=0x3f3f3f3f;
int sum[maxn],d[maxn][maxn],a[maxn];
int main(int argc, char const *argv[])
{int T,n,w; scanf("%d",&T);while(T--&&scanf("%d%d",&n,&w)==2){REP(i,1,n) scanf("%d",&a[i]);sort(a+1,a+n+1,greater<int>());REP(i,1,n) sum[i]=a[i]+sum[i-1];REP(i,1,w) REP(j,i,n-w+i) {if(i==1) d[i][j]=j*sum[j];else {d[i][j]=INF;REP(k,i-1,j-1) d[i][j]=min(d[i][j],d[i-1][k]+j*(sum[j]-sum[k]));}}double ans=(double)d[w][n]/sum[n];printf("%.4lf\n", ans);}return 0;
}