动态规划百题 第11题 POJ - 1018

Communication System

 POJ - 1018 

NUPT要建立一套系统，该系统需要n种设备，而每种设备分别可以有m1、m2、m3、...、mn个厂家提供生产，而每个厂家生产的同种设备都会存在两个方面的差别：参数和 价格。 
现在每种设备都各需要1个，考虑到性价比问题，要求所挑选出来的n件设备，要使得F/P最大。其中F为这n件设备的参数的最小值，P为这n件设备的总价。我们的目标是为每个设备选择一个制造商来最大化F / P。

Input

输入文件的第一行包含一个整数t（1≤t≤10）表示t组测试样例。每个测试样例包含单个整数n（1≤n≤100）表示系统中的设备数，后面以下的n行包含：第i行（1≤i≤n）第一个数为制造商的设备数量mi（1≤mi≤100），之后是mi对正整数，分别表示制造商对应的参数和价格。

Output

每个测试样例只包含一个数，为F / P的最大值并保留3位有效小数。

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

题解：定义dp[i][j]为前i个物件的最小带宽为j的最小价格和

然后如果j<=p，说明当前带宽小于上一个状态的带宽，dp[i][j]=min(dp[i][j],dp[i-1][j]+q)

如果j>p，说明当前带宽大于上一个状态的带宽，dp[i][p]=min(dp[i-1][j]+q,dp[i][p])

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=100+5;
int dp[maxn][maxn*maxn];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=0;i<=n;i++){
			for(int j=0;j<=1100;j++){
				dp[i][j]=INF;
			}
		}
		for(int i=1;i<=n;i++){
			int m;
			scanf("%d",&m);
			for(int k=0;k<m;k++){
				int p,q;
				scanf("%d%d",&p,&q);
				if(i==1){
					dp[i][p]=min(dp[i][p],q);
				}else {
					for(int j=0;j<=1100;j++){
						if(dp[i-1][j]!=INF){
							if(j<=p)dp[i][j]=min(dp[i-1][j]+q,dp[i][j]);
							else dp[i][p]=min(dp[i][p],dp[i-1][j]+q);
						}
					}
				}
			}
		}
		double ans=0;
		for(int i=0;i<=1100;i++){
			if(dp[n][i]!=INF){
				//cout<<i<<endl;
				//cout<<dp[n][i]<<endl;
				ans=max(i*1.0/dp[n][i],ans);
			}
		}
		printf("%.3f\n",ans);
	}
	return 0;
}