> //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;
> }

• Re:代码傻长 (26) GardenInSkyr 2011-03-26 20:34:56