LA 4731 蜂窝网络

题目链接：https://vjudge.net/problem/UVALive-4731

题意：

n 个数，分成 w 组，求整个区间的数学期望的最小值；

一个区间的数学期望公式给出：一个区间的和 * 概率

例子：

0.3 0.05 0.1 0.3 0.25 w=2

{c1,c2,c3} {c4,c5}

3*(0.3+0.05+0.1) + (3+2)*(0.3 + 0.25)

分析：

根据例子，先把较大者放到前面；d[i][j] 前 i 个数字，分成 j 组的期望；

递推公式：

d[i][j] = min(d[i][j],d[k][j]+i*(sum[i]-sum[k]));

 #include <bits/stdc++.h>

 using namespace std;

 const int inf = 0x3f3f3f3f;

 int a[];

 int sum[];

 bool cmp(int a,int b) {

     return a > b;

 }

 int d[][];

 int main() {

     int t;

     scanf("%d",&t);

     while(t--) {

         int n,w;

         scanf("%d%d",&n,&w);

         for(int i=;i<=n;i++)

             scanf("%d",&a[i]);

         sort(a+,a+n+,cmp);

         memset(d,inf,sizeof(d));

         sum[] = ;

         for(int i=;i<=n;i++)

             sum[i] = sum[i-] + a[i];

         d[][] = ;

         for(int i=;i<=n;i++) {

             for(int j=;j<=w;j++) {

                 for(int k=;k<i;k++) {

                     d[i][j] = min(d[i][j],d[k][j-]+i*(sum[i]-sum[k]));

                 }

             }

         }

         printf("%.4f\n",d[n][w]*1.0/sum[n]);

     }

     return ;

 }

巴特西

LA 4731 蜂窝网络

最新文章

热门文章