POJ 1018 Communication System（DP+離散化）

某公司要建立一套通信系統，該通信系統需要n種裝置，而每種裝置分别可以有m1、m2、m3、...、mn個廠家提供生産，而每個廠家生産的同種裝置都會存在兩個方面的差别：帶寬bandwidths 和 價格prices。

現在每種裝置都各需要1個，考慮到成本效益問題，要求所挑選出來的n件裝置，要使得B/P最大。

其中B為這n件裝置的帶寬的最小值，P為這n件裝置的總價。

思路：最多就1W個帶寬，可以對帶寬進行離散化，然後DP，dp[i][j]表示選到第i個，帶寬為j的P總和的最小值，然後狀态轉移即可

代碼：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10005;
const int INF = 0x3f3f3f3f;

int t, n, dp[2][N], hash[N], hn;

struct Man {
    
    int m, b[105], p[105];
    void read() {
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
	    scanf("%d%d", &b[i], &p[i]);
	    hash[hn++] = b[i];
	}
    }
} man[105];

int find(int x) {
    return lower_bound(hash, hash + hn, x) - hash;
}

int main() {
    scanf("%d", &t);
    while (t--) {
	hn = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) man[i].read();
	sort(hash, hash + hn);
	hn = unique(hash, hash + hn) - hash;
	memset(dp[0], INF, sizeof(dp[0]));
	for (int j = 0; j < man[1].m; j++)
	    dp[0][find(man[1].b[j])] = man[1].p[j];
	int now = 0, pre = 1;
	for (int i = 2; i <= n; i++) {
	    swap(now, pre);
	    memset(dp[now], INF, sizeof(dp[now]));
	    for (int j = 0; j < man[i].m; j++) {
		for (int k = 0; k < hn; k++) {
		    int tmp = min(find(man[i].b[j]), k);
		    dp[now][tmp] = min(dp[now][tmp], dp[pre][k] + man[i].p[j]);
		}
	    }
	}
	double ans = 0;
	for (int i = 0; i < hn; i++)
	    ans = max(ans, hash[i] * 1.0 / dp[now][i]);
	printf("%.3f\n", ans);
    }
    return 0;
}