题目链接: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;
}
分享到:
相关推荐
It's the sample code of getting cellular network information in android os.
Expression and sub-cellular localization of leucine-rich repeats and immunoglobulin-like domain 1 is related to antioxidant enzymes in human ependymoma and oligodendroglioma,易伟,刘琳,The current ...
Qualcomm-Cellular-V2X-AESIN-Oct-2016
us-18-Shattuck-Snooping-on-Cellular-Gateways-and-Their-Critical-Role-in-ICS 解决方案 威胁情报 安全研究 应急响应 安全架构
Final-report-for-5GAA-on-cellular-V2X-socio-economic-benefits-051217_FINAL.pdf
Qualcomm-Cellular-V2X-AESIN-Oct-2016.pptx
Qualcomm-Cellular-V2X-AESIN-Oct-2016.pdf
数学建模-cellular programm.zip
数学建模-cellular paradingms.zip
关于Qualcomm-Cellular-V2X-AESIN-Oct-2016的介绍说明.rar
数学建模-Cellular Automata in Matlab.zip
control in both uplink and downlink of a cellular network has been extensively studied, especially over the last 15 years, and some of the results have enabled the continuous evolution and significant...
设备到设备(Device-to-device D2D)通信是一种很有前途的提高蜂窝网络频谱效率的技术网络。在本文中,我们研究了联合上行链路和下行资源分配问题的总和最大化在保证服务质量的同时保证系统的数据速率(QoS)蜂窝用户...
Filling this void, Evolved Cellular Network Planning and Optimization for UMTS and LTE presents an accessible introduction to all stages of planning and optimizing UMTS, HSPA, and LTE cellular ...
Conference on Cellular Automata for Research and Industry, held at the University of Karlsruhe (Germany), 4 - 6 October, 2000. The continuation of and growing interest in research on Cellular Automata...
+---.gitignore +---LICENSE +---README.md +---project.godot +---default_env.tres +---assets/ \---logo.png \---src/ +---main.tscn \---main.gd 时间线 2021年2月6日-移植到gdscript。 2020年12月24日-创建...
ST的X-CUBE-CELLULA是stm32cube的扩展,里面包含了2G, 3G, LTE Cat M1, NB-IoT的使用例程