首页 > 代码库 > LA 4731 蜂窝网络

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]));

技术分享
 1 #include <bits/stdc++.h> 2  3 using namespace std; 4  5 const int inf = 0x3f3f3f3f; 6  7 int a[105]; 8 int sum[105]; 9 bool cmp(int a,int b) {10     return a > b;11 }12 13 int d[105][105];14 15 16 int main() {17 18     int t;19     scanf("%d",&t);20     while(t--) {21 22         int n,w;23         scanf("%d%d",&n,&w);24         for(int i=1;i<=n;i++)25             scanf("%d",&a[i]);26 27         sort(a+1,a+n+1,cmp);28         memset(d,inf,sizeof(d));29 30         sum[0] = 0;31         for(int i=1;i<=n;i++)32             sum[i] = sum[i-1] + a[i];33 34         d[0][0] = 0;35         for(int i=1;i<=n;i++) {36             for(int j=1;j<=w;j++) {37                 for(int k=0;k<i;k++) {38                     d[i][j] = min(d[i][j],d[k][j-1]+i*(sum[i]-sum[k]));39                 }40             }41         }42 43         printf("%.4f\n",d[n][w]*1.0/sum[n]);44 45     }46 47 48     return 0;49 }
View Code

 

LA 4731 蜂窝网络