题目描述

奶龙???有 $N$ 块木板，第 $i$ 块木板的长度为 $L_i$，它们要用这些木板作为栅栏，围出一个三角形的牧场。

所有的木板都必须用上，不得浪费。她们聘请你为设计师，请你帮助它们围出一个尽量大的三角形。

输入格式

• 第一行：单个整数 $N$，3  \le N  \le 40

• 第二行到第 $N + 1$ 行：第 $i + 1$ 行有一个整数 $L_i$，1  \le L_i  \le 40

输出格式

• 单个整数：表示最大三角形面积 $* 100$ 取整数。如果用这些木板无法搭出任何三角形，输出 $−1$

输入输出样例

输入 #1

5
1
1
3
3
4

输出 #1

692

样例解释

面积最大的是边长为 $4$ 的等边三角形

提示

注意精度问题！！！海伦公式请全程double！！！

Hint

#include<bits/stdc++.h>
using namespace std;
const int N=45, M=1620;
int a[N], f[2][M][M];
bool pd(int i, int j, int k){
	if(i+j<=k || abs(i-j)>=k) return 0;
	if(i+k<=j || abs(i-k)>=j) return 0;
	if(j+k<=i || abs(k-j)>=i) return 0;
	if((i<=0) || (j<=0) || (k<=0)) return 0;
	return 1;
}
double calc(double i, double j, double k){
	double p=(i+j+k)/2;
	double res=sqrt(p*(p-i)*(p-j)*(p-k))*100.0;
	return res;
}
int main(){
	int n, sum=0; scanf("%d", &n);
	for(int i=1; i<=n; i++){
		scanf("%d", &a[i]);
		sum+=a[i];
	}
	double ans=0;
	memset(f, 0, sizeof(f)); f[0][0][0]=1;
	for(int i=1; i<=n; i++){
		for(int j=0; j<=sum/2; j++){
			for(int k=0; k<=sum/2; k++) if(f[(i-1)&1][j][k]){
				f[i&1][j+a[i]][k]=1;
				f[i&1][j][k+a[i]]=1;
				f[i&1][j][k]=1; 
			int t=sum-k-j-a[i];
			if(pd(j+a[i]&#44; k&#44; t)) ans=max(ans&#44; calc(j+a[i]&#44; k&#44; t));
			if(pd(j&#44; k+a[i]&#44; t)) ans=max(ans&#44; calc(j&#44; k+a[i]&#44; t));
		}
	}
}
printf("%d\n"&#44; (!ans)? -1: (int)ans);
return 0;

}