首页 > 代码库 > POJ 1018 Communication System（DP）
POJ 1018 Communication System（DP）
http://poj.org/problem?id=1018
题意：
某公司要建立一套通信系统，该通信系统需要n种设备，而每种设备分别可以有m1、m2、m3、...、mn个厂家提供生产，而每个厂家生产的同种设备都会存在两个方面的差别：带宽bandwidths 和 价格prices。
现在每种设备都各需要1个，考虑到性价比问题，要求所挑选出来的n件设备，要使得B/P最大。
其中B为这n件设备的带宽的最小值，P为这n件设备的总价。
思路：DP解决。
d[i][j]代表选择第i个设备时最小带宽j时的价格。
状态转移方程就是d[i][j]=min{d[i-1][k]+p,d[i][j]}。
#include<iostream> #include<cstring>#include<algorithm>#include<cmath>#include<iomanip>using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 100 + 5;int n,m;int dp[maxn][12000];int main(){ //freopen("D:\\txt.txt", "r", stdin); int t, b, p; cin >> t; while (t--) { memset(dp, INF, sizeof(dp)); cin >> n; for (int i = 0; i < n; i++) { cin >> m; for (int j = 0; j < m; j++) { cin >> b >> p; if (i == 0) dp[i][b] = p; else { for (int k = 0; k < 1100; k++) { if (dp[i - 1][k] != INF) { if (k <= b) dp[i][k] = min(dp[i - 1][k] + p, dp[i][k]); else dp[i][b] = min(dp[i - 1][k] + p, dp[i][b]); } } } } } double ans = 0; for (int k = 0; k < 1100; k++) { if (dp[n - 1][k] != INF) { double c = (double)k / dp[n - 1][k]; if (c>ans) ans = c; } } cout << setiosflags(ios::fixed) << setprecision(3) << ans << endl; } return 0;}
POJ 1018 Communication System（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。