题意：有n个数字u1,u2,u3…un，每一个数字出现的概率pi = ui/(u1 + u2 + … + un)，分成w组。计算期望值。

第一组例子的五个数字例如以下

30 5 10 30 25

分成2组

假设分成{u1, u2, u3}和{u4,u5}

期望值 = 3 * (p1 + p2 + p3) + (3 + 2) * (p4 + p5)

假设分成{u1,u4}和{u2,u3,u5}

期望值 = 2 * (p1 + p4) + (2 + 3) * (p2 + p3 + p5)

求最小的期望值。

题解：能够得到结论，概率大的值先计算概率值更小。所以先要把概率从大到小排序。这样分组都是连续的一段。

dp：f[i][j]表示前i个数字分为j组的最小期望值。

那么f[i][j] = min(f[i][j], f[k - 1][j - 1] + sum[k][i] * i)

当中1 <= k <= i，表示划分了k到i这一段当成一组。

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 105;const double INF = 0x3f3f3f3f;int n, w, u[N];double p[N], f[N][N], sum[N];bool cmp(double a, double b) {    return a - b > 1e-9;}int main() {    int t;    scanf("%d", &t);    while (t--) {        memset(sum, 0, sizeof(sum));        scanf("%d%d", &n, &w);        int Sum = 0;        for (int i = 1; i <= n; i++) {            scanf("%d", &u[i]);            Sum += u[i];        }        sort(u + 1, u + n + 1, cmp);        for (int i = 1; i <= n; i++) {            p[i] = u[i] * 1.0 / Sum;            sum[i] = sum[i - 1] + p[i];        }        for (int i = 0; i <= n; i++)            for (int j = 0; j <= w; j++)                if (i == 0)                    f[i][j] = 0;                else                    f[i][j] = INF;        for (int i = 1; i <= n; i++)            for (int j = 1; j <= w; j++)                for (int k = 1; k <= i; k++)                    f[i][j] = min(f[i][j], f[k - 1][j - 1] + i * (sum[i] - sum[k - 1]));        printf("%.4lf\n", f[n][w]);    }    return 0;}