【dp】poj 1018 Communication System

/* poj 1018 Communication System 题意：在n行里，每行里有mi个运输机，从一行选择一个，最后算得选择的运输机min(B)/sum(P)，使之最大。 题解： dp[i][j]代表前i行，min(B)为j的最小花费钱。 注意有意义的j个数是变化的。 if(b[i] >= j) dp[j] = min(dp[j],ans+p[i]); else dp[b[i]] = min(dp[b[i]],ans+p[i]); */ #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <vector> #include <map> #include <queue> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; const int N = 1510; int b[N],p[N]; int dp[N]; int ans[N]; int main() { int T; cin >> T; while(T--) { for(int i = 0; i < N; i++) dp[i] = INF; int n,m; cin >> n >> m; queue<int> Q; for(int j = 0; j < m; j++) { cin >> b[j] >> p[j]; dp[b[j]] = min(dp[b[j]],p[j]); ans[b[j]] = dp[b[j]]; Q.push(b[j]); } for(int i = 1; i < n; i++) { for(int j = 0; j < N; j++) dp[j] = INF; cin >> m; for(int j = 0; j < m; j++) cin >> b[j] >> p[j]; int len = Q.size(); while(len--) { int f = Q.front(); Q.pop(); int flag = 0; for(int j = 0; j < m; j++) { if(b[j] >= f) { dp[f] = min(dp[f],ans[f]+p[j]); flag = 1; } else dp[b[j]] = min(dp[b[j]],ans[f]+p[j]); } if(flag) Q.push(f); } for(int j = 0; j < m; j++) if(dp[b[j]] != INF) Q.push(b[j]); for(int j = 0; j < N; j++) ans[j] = dp[j]; } double answer = 0; while(!Q.empty()) { int x = Q.front(); Q.pop(); double f = x*1.0/ans[x]; answer = max(answer,f); } printf("%.3lf\n",answer); } return 0; }