poj1018 Communication System

Description

We have received an order from Pizoor Communications Inc. for a special communication system. The system consists of several devices. For each device, we are free to choose from several manufacturers. Same devices from two manufacturers differ in their maximum bandwidths and prices. By overall bandwidth (B) we mean the minimum of the bandwidths of the chosen devices in the communication system and the total price (P) is the sum of the prices of all chosen devices. Our goal is to choose a manufacturer for each device to maximize B/P.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. Each test case starts with a line containing a single integer n (1 ≤ n ≤ 100), the number of devices in the communication system, followed by n lines in the following format: the i-th line (1 ≤ i ≤ n) starts with mi (1 ≤ mi ≤ 100), the number of manufacturers for the i-th device, followed by mi pairs of positive integers in the same line, each indicating the bandwidth and the price of the device respectively, corresponding to a manufacturer.

Output

Your program should produce a single line for each test case containing a single number which is the maximum possible B/P for the test case. Round the numbers in the output to 3 digits after decimal point.

Sample Input

1 3
3 100 25 150 35 80 25
2 120 80 155 40
2 100 100 120 110

Sample Output

0.649
这道题的题目一开始令我难以理解，不知道题目想干什么。后来才明白是去挑设备，使得带宽B的最小值，以及价格P的和的比值B/P达到最小
一开始的想法比较想当然，对每一层的每个设备，挑出使得所求值最小的上一层的设备，dp[i][j]表示第i层j个厂商的B值和sum(P),代码是这样的：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #define N 102
 6 #define M 102
 7 
 8 int count[N];
 9 struct Dpr{
10     int B;
11     int P;
12 };
13 Dpr man[N][M];
14 Dpr dp[N][M];
15 
16 double min(int a, int b) {
17     if(a <= b) {
18         return (double)a;
19     }
20     else {
21         return (double)b;
22     }
23 }
24 int main(int argc, char const *argv[])
25 {
26     int ci,n;
27     freopen("input.txt","r",stdin);
28     scanf("%d",&ci); 
29     while(ci--) {
30         scanf("%d",&n);
31         for(int i = 0; i < n; i++) {
32             scanf("%d",&count[i]);
33             for(int j = 0; j < count[i]; j++) {
34                 scanf("%d %d",&man[i][j].B,&man[i][j].P);
35             }
36         }
37         for(int j = 0; j < count[0]; j++) {
38             dp[0][j] = man[0][j]; 
39         }
40         for(int i = 1; i < n; i++) {
41             for(int k = 0; k < count[i]; k++) {
42                 double minB = min(dp[i-1][0].B,man[i][k].B);
43                 double maxP = dp[i-1][0].P + man[i][k].P;
44                 double maxi = minB / maxP;
45 
46                 for(int j = 1; j < count[i-1];j++) {
47                     double minBj = min(dp[i-1][j].B,man[i][k].B);
48                     double maxPj = dp[i-1][j].P + man[i][k].P;
49                     double maxj = minBj / maxPj; 
50                     if(maxj > maxi) {
51                         maxi = maxj;
52                         minB = minBj;
53                         maxP = maxPj;
54                     }
55                 }
56                 dp[i][k].B = minB;
57                 dp[i][k].P = maxP;
58                 printf("%lf %lf	",minB,maxP);
59             }
60             
61              printf("
");
62         }
63         double minB = dp[n-1][0].B;
64         double maxP = dp[n-1][0].P;
65         double maxn = minB / maxP;
66         
67         for(int i = 1; i < count[n-1]; i++) {
68             double minBi = dp[n-1][i].B;
69             double maxPi = dp[n-1][i].P;
70             double maxi = minBi / maxPi;
71             if(maxi > maxn) {
72                 maxn = maxi;
73             }
74         }
75         printf("%.3lf
",maxn);
76     }
77     return 0;
78 }

但这样做结果是错误的，因为不同层次之间还是有关的，不能完全割裂。

后来将其修改为如下代码，dp[i][j]表示带宽为i时sum(p)的最小值

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #define N 102
 6 #define M 102
 7 #define BMAX 1100
 8 #define MAX 9999999
 9 int count[N];
10 struct Dpr{
11     int B;
12     int P;
13 };
14 Dpr man[N][M];
15 int dp[N][BMAX];//save price
16 
17 int min(int a, int b) {
18     if(a <= b) {
19         return (double)a;
20     }
21     else {
22         return (double)b;
23     }
24 }
25 int main(int argc, char const *argv[])
26 {
27     int ci,n;
28     //freopen("input.txt","r",stdin);
29     scanf("%d",&ci); 
30     while(ci--) {
31         scanf("%d",&n);
32         for(int i = 0; i < n; i++) {
33             scanf("%d",&count[i]);
34             for(int j = 0; j < count[i]; j++) {
35                 scanf("%d %d",&man[i][j].B,&man[i][j].P);
36             }
37             for(int k = 0; k < BMAX; k++) {
38                 dp[i][k] = MAX;
39             }
40         }
41         for(int j = 0; j < count[0]; j++) {
42             dp[0][man[0][j].B] = man[0][j].P; 
43         }
44         
45         for(int i = 1; i < n; i++) {
46             for(int j = 0; j < count[i]; j++) {
47                 for(int k = 0; k < BMAX; k++) {
48                     if(dp[i-1][k] != MAX) {
49                         if(k <= man[i][j].B) {
50                             dp[i][k]=min(dp[i][k],dp[i-1][k]+man[i][j].P);  
51                         }
52                         else {
53                             dp[i][man[i][j].B]=min(dp[i][man[i][j].B],dp[i-1][k]+man[i][j].P);  
54                         }
55                     }
56                 }
57             }
58             
59         }
60         
61         double max = 0;
62         for(int k = 0; k < BMAX; k++) {
63             if(dp[n-1][k] != MAX) {
64                 //printf("%d
",dp[n-1][k]);
65                 double maxk =  (double)k/(double)dp[n-1][k];
66                 if(max < maxk) {
67                     max = maxk;
68                 }
69             }
70         }
71                
72         printf("%.3lf
",max);
73     }
74     return 0;
75 }

至于BMAX是1100，是参考了其他人的解题报告，至于有没有更好的办法，还需要再去考虑