首页 > 代码库 > 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 }
LA 4731 蜂窝网络
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。