【poj1018】 Communication System

http://poj.org/problem?id=1018 (题目链接)

题意

　　要买n个产品，每个产品有m种价格和宽度(我也不知道翻译过来到底是什么?），设n个产品的宽度的最小值为B，n个产品的价格和为P，要求B/P最大。

Solution

　　dp。题目没说B的取值范围，坑死了。

　　f[i][j]表示前i个产品，当B为j时的最小价格。

　　转移很好转，具体见代码。

代码

// poj1018
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cmath>
#include<map>
#define MOD 100003
#define inf 2147483640
#define LL long long
#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
using namespace std;

const int maxn=110;
int f[maxn][maxn*maxn],n,m;

int main() {
	int T;scanf("%d",&T);
	while (T--) {
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
			for (int j=0;j<1100;j++) f[i][j]=inf;
		for (int m,i=1;i<=n;i++) {
			scanf("%d",&m);
			for (int b,p,j=1;j<=m;j++) {
				scanf("%d%d",&b,&p);
				if (i==1) f[i][b]=min(f[i][b],p);
				else for (int k=0;k<1100;k++) if (f[i-1][k]!=inf) {
							if (k<=b) f[i][k]=min(f[i][k],f[i-1][k]+p);
							else f[i][b]=min(f[i][b],f[i-1][k]+p);
						}
			}
		}
		double ans=0;
		for (int i=0;i<1100;i++)
			if (f[n][i]!=inf) ans=max(ans,(double)i/f[n][i]);
		printf("%.3f
",ans);
	}
	return 0;
}