动态规划百题 第11题 POJ - 1018
Communication System
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;
}
