POJ1018

//POJ 1018(DP) 当有俩个变量时可固定一个边量再去求另一个变量(important)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define inf (0x3f3f3f3f)
using namespace std;
int dp[115][1200];//前i个的设备的j带宽的最小价钱
int main()
{
    int t,n,m;  cin>>t;
    while(t--)
    {
        memset(dp,inf,sizeof(dp));
        int b,p;
        cin>>n;
        for(int i=1;i<=n;++i)
        {
            cin>>m;
            while(m--)
            {
                cin>>b>>p;
                if(i==1)
                    dp[1][b] = min(dp[1][b],p);
                else{
                    for(int j=0;j!=1200;++j)
                    {//对于每一个带宽
                        if(dp[i-1][j]!=inf)//如果上一层有这个最小带宽的值
                        {
                            if(j<=b)
                                dp[i][j] = min(dp[i][j],dp[i-1][j]+p);
                            else
                                dp[i][b] = min(dp[i][b],dp[i-1][j]+p);
                        }
                    }
                }
            }
        }
        double maxValue = 0;
        for(int i=0;i!=1200;++i)
        {
            double tmp = (double)i/dp[n][i];
            maxValue = max(maxValue,tmp);
        }
        printf("%.3lf
",maxValue);
    }
}