记录编号	45542	评测结果	AAAAAAAAAAA
题目名称	三角形牧场	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.371 s
提交时间	2012-10-24 14:28:08	内存使用	5.11 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
 
int a[50],s[50];
bool f[1610][1610];
 
void swap(int& a,int& b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}
 
double cal(int a,int b,int c)
{
	if (b>c)
		swap(b,c);
	if (a>b)
		swap(a,b);
	if (b>c)
		swap(b,c);
	if (a+b<c||a==0)
		return(0);
	double p,ans=0;
	p=(a+b+c)/2.0;
	ans=sqrt(p*(p-a)*(p-b)*(p-c));
	return(ans);
}
 
int main(void)
{
	freopen("pasture.in","r",stdin);
	freopen("pasture.out","w",stdout);
	int i,j,k,n;
	double maxs=0,temp;
	cin>>n;
	for (i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	f[0][a[1]]=true;
	f[a[1]][0]=true;
	f[0][0]=true;
	for (i=2;i<=n;i++)
		for (j=s[i];j>=0;j--)
			for (k=s[i];k>=0;k--)
			{
				if (j-a[i]>=0)
					if (f[j-a[i]][k])
						f[j][k]=true;
				if (k-a[i]>=0)
					if (f[j][k-a[i]])
						f[j][k]=true;
			}
	for (i=1;i<=s[n];i++)
		for (j=1;j<=s[n];j++)
			if (f[i][j])
			{
				temp=cal(i,j,s[n]-i-j);
				if (maxs<temp)
					maxs=temp;
			}
	if (maxs==0)
		cout<<"-1\n";
	else
		cout<<int(maxs*100)<<endl;
	return(0);
}