poj1018 Communication System

xiaoxiao2021-02-28  9

//题意:第一行给你两个数字,第一个是T组数据,第二个数n是接下来有几行,每一行第一个m代表这一行有几组值,d,p分别代表带块(跟家里的宽带最大允许通过字节数差不多意思)和价格,问:每一行代表一个设备,每个设备有m个厂商提供自己的产品,每一类设备选择一个厂商,共选n个设备,然后因为一个设备选择一个厂商,在这些厂商中选择一个d,带宽最小值,求得d/(p1+p2+...+pn)最大值,例如样例:第一行:150 35;第二行 155 40; 第三行:120 110  则最小值d为120  ,120/(35+40+110)即0.649

//【注意】:此题真的好恶心,跟自己菜有关系,一直按照这个思路写好的代码就是过不了,后来从新按照同样思路写了好多次写了一天终于过去了,并得到一个结论:思路决定一切,看似完全相同的代码并不代表思路相同,按照自己思路写出自己的代码,可以看题解,但要知道的是借别人的思路写出自己的代码)

//思路:这个题有多解,这里是dp解法,看到此题应该想到动态转移,那么关于求 d/p的最大值有个简单的贪心思路是尽量不断状态压缩保证p的总和相对较小,但是并不代表p越小就是题目的解,因为题目有另一不可控变量d,状态压缩同时将所有情况保存起来,所以此题关键并不是贪心求出p的最小值,而是保存所有的状态,因为d和p均为变量,只能球的所有状态一一枚举计算,当然求p有利于更快速求得答案,这里的动态方程非常简单不多说,见代码:

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int const maxx = 1200; int dp[120][maxx]; int vis[maxx]; int main() { int t; scanf("%d", &t); while(t--){ int n; scanf("%d", &n); memset(dp, 1000000, sizeof(dp)); memset(vis, 0, sizeof(vis)); for(int i = 0; i < maxx; i++) dp[0][i] = 0; int max_d = 0; for(int i = 1; i <= n; i++){ int m; scanf("%d", &m); for(int j = 0; j < m; j++){ int d, p; scanf("%d%d", &d, &p); max_d = max(max_d, d); vis[d] = 1; for(int k = d; k < maxx; k++){ dp[i][d] = min(dp[i][d], dp[i-1][k] + p);//尽可能状态压缩求出些相对较小的p } for(int k = 0; k < d; k++){ dp[i][k] = min(dp[i-1][k] + p, dp[i][k]);//此题关键是这里和上面两步将所有状态都保存起来 } } } float ans = -1; for(int i = 0; i <= max_d; i++){ if(vis[i] && ans < (i/(float)dp[n][i])){  //这里一一运算求出最大值即可 ans = i/(float)dp[n][i]; } } printf("%.3f\n", ans); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-2800234.html

最新回复(0)