UVALive 4731 Cellular Network（贪心，dp）

分析：

状态是一些有序的集合，这些集合互不相交，并集为所有区域。显然枚举集合元素是哪些是无法承受的，

写出期望的计算式，会发现，当每个集合的大小确定了以后，概率大的优先访问是最优的。

因此先对u从大到小排序。定义状态f[i][j]表示从j开始往后分i组的最小期望。

转移是枚举划分k，则有f[i][j] = min{f[i-1][k]+(k-j)*(sum_u(j,n))}，k>j

边界f[1][j] = (n-j+1)*(u[j])

处理出u的前缀和

复杂度O(w*n^2)

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100+4;
int u[maxn];
int f[101][maxn];
const int INF = 0x3f3f3f3f;

//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    int T; cin>>T;
    while(T--){
        int n,w; scanf("%d%d",&n,&w);
        for(int i = 1; i <= n; i++) scanf("%d",u+i);
        sort(u+1,u+1+n,greater<int>());
        for(int i = 1; i <= n; i++) u[i] += u[i-1];
        for(int j = n; j > 0; j--){
            f[1][j] = (n-j+1)*(u[n]-u[j-1]);
        }
        for(int i = 2; i <= w; i++){
            for(int j = 1; j <= n; j++){
                f[i][j] = INF;
                for(int k = j+1; k <= n; k++){
                    f[i][j] = min(f[i-1][k]+(k-j)*(u[n]-u[j-1]),f[i][j]);
                }
            }
        }
        printf("%.4lf
", f[w][1]/(double)u[n]);
    }
    return 0;
}