题目地址：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; }
