#include <stdio.h>
#include <iomanip>
#include <climits>
#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
	int t;
	int n;
	int m[100];
	int b[100][100];
	int p[100][100];
	int total;
	int B[10000];//record the possible answer for the minimal bandwidth of the communication system
	double Dec[10000];//record B/P
	int len_B;
	int i,j,k;

	scanf("%d",&t);

	while(t>0)
	{
		//n: there have n pieces of devices
		scanf("%d",&n);

		//resert the data value for different cases
		len_B = 0;
	

		//this paragraph is to make the input data correct
		for( int i = 0; i < n ; i++ )
		{
			scanf("%d",&m[i]);
			for( int j = 0; j < m[i]; j++ )
			{
				scanf("%d %d",&b[i][j],&p[i][j]);
				B[len_B] = b[i][j];
				len_B ++;
			}
		}

		for(  i = 0; i < len_B; i++ )
		{
			total = 0;//for each case of B[i],we should reset the value of total peice to 0.
	
			for(  j = 0; j < n; j++ )
			{
				int temp = INT_MAX;	
				
				for(  k = 0; k < m[j]; k++ )
				{
					if( b[j][k] >= B[i] &  p[j][k] < temp )
					{							
							temp = p[j][k];
					}
				}//for_k

				if( temp != INT_MAX)
					total += temp;
				else 
					total = INT_MIN;
			}//for_j

			if( total > 0 )
				Dec[i] =((double) B[i])/((double) total);
			else
				Dec[i] = -1;
		}//for_i

		double max = -1;
		for( i = 0; i < len_B; i++ )
			if( Dec[i] > max )
			{
				max = Dec[i];	
			}

		cout << setiosflags(ios::fixed) << setprecision(3) << max << endl;
		

			t--;
	}

	return 0;
}

• Re:我在pku上的第一道dp题（附程序） (116) NomadThanatos 2009-04-14 18:31:49
• Re:我在pku上的第一道dp题（附程序） (1751) chenyukang 2009-06-29 17:20:57
• Re:我在pku上的第一道dp题（附程序） (1735) thscut 2009-06-29 18:05:16
  • Re:我在pku上的第一道dp题（附程序） (10) Zenomyth 2009-11-14 20:22:57
    • Re:我在pku上的第一道dp题（附程序） (28) huntmind 2010-06-19 11:02:01