#include<iostream>
using namespace std;
#define MAX 0x7fffffff;
struct ff
{
	int price;
	int brand;
}f[101][101];

int dp[101][10000];
int MMIN(int a,int b)
{
	if(a>b)
		return b;
	return a;
}

int main()
{
	int bb[100000]={0};
	int t,n,m[101];
	int i,j,k;
	int mmin,mmax;
	double ans;
	cin>>t;
	while(t--)
	{
		cin>>n;
		memset(bb,0,sizeof(bb));
		mmin=MAX;
		mmax=-111111;

		for(i=0;i<n;i++)
		{
			scanf("%d",&m[i]);
			for(j=0;j<m[i];j++)
			{
				scanf("%d%d",&f[i][j].brand,&f[i][j].price);
				bb[f[i][j].brand]=1;
				if(f[i][j].brand>mmax)
					mmax=f[i][j].brand;
				if(f[i][j].brand<mmin)
					mmin=f[i][j].brand;
			}
		}
	//	memset(dp,0,sizeof(dp));
		for(i=0;i<n;i++)
			dp[i][mmin-1]=MAX;
		for(j=0;j<n;j++)
		{
			for(i=mmin;i<=mmax;i++)
			{
				dp[j][i]=MAX;
				for(k=0;k<m[j];k++)
				{
					if(f[j][k].brand>=i&&bb[i]==1)
						dp[j][i]=MMIN(dp[j][i],dp[j-1][i]+f[j][k].price);
				}
			}
		}
		ans=0;
		for(i=mmin;i<=mmax;i++)
		{
			if(i*1.0/dp[n-1][i]>ans)
				ans=i*1.0/dp[n-1][i];
		}
		printf("%.3lf\n",ans);
	}
	return 0;
}

• Re:那位大牛帮忙看看啊 小弟不胜感激 折腾了两天了 不知道哪里错了。。。。。 (82) dirtysalt 2009-07-15 00:28:01
  • Re:那位大牛帮忙看看啊 小弟不胜感激 折腾了两天了 不知道哪里错了。。。。。 (18) starvae 2009-07-16 20:49:06
    • Re:那位大牛帮忙看看啊 小弟不胜感激 折腾了两天了 不知道哪里错了。。。。。 (255) dirtysalt 2009-07-17 11:57:59