首页 > Web开发 > 详细

uva 1456 - Cellular Network(dp + 贪心)

时间:2014-02-20 13:06:15      阅读:328      评论:0      收藏:0      [点我收藏+]

题目链接:uva 1456 - Cellular Network


题目大意:给出n和w,表示有n台机器,以及n个概率p[i](注意概率是p[i]/sum),现在将n台机器分成w组,按照题目中的公式计算值,要求找出最小的值。


解题思路:先贪心,因为概率大的肯定放前面优,因为放后面乘的dp[i][j]表示第i个机器分成j组后的最小值,dp[i][j] = min{dp[k][j-1] + (s[i]-s[k])/sum*i}.


#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>

using namespace std;
const int N = 105;
const double INF = 0x3f3f3f3f3f3f3f3f;

int n, w, sum, s[N], p[N];
double dp[N][N];

bool cmp(const int& a, const int& b) {
	return a > b;
}

void init () {
	sum = s[0] = 0;
	scanf("%d%d", &n, &w);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &p[i]);
		sum += p[i];
	}
	sort(p+1, p+n+1, cmp);
	for (int i = 1; i <= n; i++)
		s[i] = s[i-1] + p[i];
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= w; j++) dp[i][j] = INF;
}

double solve () {
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i && j <= w; j++) {
			dp[i][j] = INF;
			for (int k = j-1; k < i; k++)
				dp[i][j] = min(dp[i][j], dp[k][j-1] + (s[i]-s[k])/(sum*1.0)*i);
		}
	}
	return dp[n][w];
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init();
		printf("%.4lf\n", solve());
	}
	return 0;
}


uva 1456 - Cellular Network(dp + 贪心)

原文:http://blog.csdn.net/keshuai19940722/article/details/19507695

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!