题意:n(1 ≤ n ≤ 100)种设备,第i种设备可由mi(1 ≤ mi ≤ 100)个制造商提供,每种设备的标准有带宽和价格,n种设备的总带宽是所有带宽的最小值,总价格的所有设备的价格和,求最小的总带宽/总价格。
题目链接:http://poj.org/problem?id=1018
——>>一方面是最大带宽,一方面的最大总价,两方面最优,让其中一项作数组的下标,一项作数组元素的值。。
设d[i][j]表示选好了前i种设备时最小带宽为j的最小总价。。
状态转移方程:d[i][min(j, bw[k])] = d[i-1][j] + p[k], k = 1, 2, ..., mi。。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100 + 10; const int maxw = 1000 + 10; const int INF = 0x3f3f3f3f; int n, m, bw[maxn], p[maxn]; int d[maxn][maxw]; //第二维较危险 int maxbw; void readdp() { scanf("%d", &n); maxbw = -1; memset(d, 0x3f, sizeof(d)); for(int i = 1; i <= n; i++) { scanf("%d", &m); for(int j = 1; j <= m; j++) { scanf("%d%d", bw+j, p+j); maxbw = max(maxbw, bw[j]); } if(i == 1) { for(int j = 1; j <= m; j++) d[1][bw[j]] = min(d[1][bw[j]], p[j]); continue; } for(int j = 0; j <= maxbw; j++) { if(d[i-1][j] != INF) { for(int k = 1; k <= m; k++) { if(d[i-1][j] + p[k] < d[i][min(j, bw[k])]) { d[i][min(j, bw[k])] = d[i-1][j] + p[k]; } } } } } } void output() { double Max = -1; for(int i = 0; i <= maxbw; i++) { if(d[n][i] != INF) { Max = max(Max, (double)i / d[n][i]); } } printf("%.3f\n", Max); } int main() { int t; scanf("%d", &t); while(t--) { readdp(); output(); } return 0; }