> #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题（附程序） (10) Zenomyth 2009-11-14 20:22:57
  • Re:我在pku上的第一道dp题（附程序） (28) huntmind 2010-06-19 11:02:01