//pku 1948 Triangular Pastures
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
bool use[40][1000][1000] = {false};
int segment[40];
float half;
double getarea(int a,int b,int c)
{
	return (half * (half - a) * (half - b )* (half -c));
}
main()
{
	int sum = 0;
	int n;
	int i,j,k;
	int third;
	int min = 100;
	scanf("%d",&n);
	for(i = 0 ; i < n ; i++)
	{
		scanf("%d",&segment[i]);
		sum += segment[i];
	//	if(min > segment[i]) min = segment[i];
	}
	half = float(sum/2.0) ;
	use[0][segment[0]][0] = true;
	use[0][0][segment[0]] = true;
	int flag ;
	for(k = 1 ; k< n ; k++)
	{
		flag = 0;
	//	printf("------------------------------------\n");
	//	printf("%d  \n",k);
		for(i = 0; i<= half; i++)
		{
			for(j = 0; j<=half; j++)
			{
				if(use[k-1][i][j])
				{
					flag = 1;
					use[k][i][j] = true;
					if(i+segment[k]<=half)
					    use[k][i+segment[k]][j] = true;
					if(j+segment[k]<=half)
				    	use[k][i][j+segment[k]] = true;
			//		printf("%d ,%d : %d %d\n",i+segment[k],j,i,j+segment[k]);
				}
			}
		}
//		if(flag == 0)
//			flag = 0;
	}
	double max = -1; 
	double area;
	for(i = 0 ; i<=half; i++)
	{
		for(j = 0 ; j<=half ; j++)
		{
			if(use[n-1][i][j])
			{
				third = sum - i - j; 
				if(third >=i+j )
					continue;
				if(i>=j+third)
					continue;
				if(j >= i+third)
					continue;
				area = getarea(i,j,third);
	//			printf("area %d \n",area);
				if(area > max)
				{
					max = area;
				}
			}
			
		//	if(use[n-1][i][j])
	      //  printf("%d  %d \n",i,j);
		}
	}
	max = sqrt(max) * 100;
//	cout<<(int)(max*100)<<endl;
	printf("%I64d\n",(__int64)(max));
//	cout<<area
	return 1;
}

• 代码傻长 (1877) 117474335 2010-09-26 22:58:06
  • Re:代码傻长 (26) GardenInSkyr 2011-03-26 20:34:56