三角形牧场

首先分析题目
要计算三角形面积，给的条件有边
肯定要想到海伦公式了

$p=(a+b+c)/2$
$S=\sqrt{p\ast (p-a)\ast (p-b)\ast (p-c)}$

然后分析状态
每个木板存在三种状态
1.在第一条边上
2.在第二条边上
3.在第三条边上
这三个状态直接决定了这三条边能不能构成三角形
那么就可以列出状态转移
f[i][j][k][l]表示前i条木板，三条边分别为在i，j，k时是否可以构成三角形
然后问题来了
发现$40\ast 800\ast 800\ast 800$数组肯定开不了那么大（800的意思就是 三角形的任何一条边肯定小于总周长的一半）


欸？周长？


因为要把所有木板用完，所以周长是不变的，我们只需表示两条边第三套边用周长得到就行了


下面看代码理解吧

#include <iostream>
#include <cmath>

#define dou double
#define ll long long

using namespace std;

const int N = 101;

int a[N];
bool f[41][888][888]; // 前i块木板放在第j块或者放在第k块或者放在另一块能否能构成三角形 

bool istl(dou a, dou b, dou c)// 判断三角形
{
	if(a + b > c && a + c > b && c + b > a) return 1;
	return 0;
}

double helen(dou a, dou b, dou c)// 海伦公式求面积
{
	dou p = (a + b + c) / 2;
	return sqrt(p * (p - a) * (p - b) * (p - c));
}
int main()
{
	int n;
	cin >> n;
	int sum = 0;//周长
	for(int i = 1; i <= n; i ++)
		cin >> a[i], sum += a[i];
	
	f[0][0][0] = 1;
		
	for(int i = 1; i <= n; i ++)
		for(int j = 0; j <= sum / 2; j ++)// sum/2 显然每条边超不过周长的一半 
			for(int k = 0; k <= sum / 2; k ++)
			{
				if(j >= a[i] && f[i - 1][j - a[i]][k]) f[i][j][k] = 1; // 放在第一个边 
				
				if(k >= a[i] && f[i - 1][j][k - a[i]]) f[i][j][k] = 1; // 放在第二个边
				
//				if(f[i - 1][j][k]) f[i][j][k] = 1;	  // 放在第三个边 
			} 
	
	dou ans = -1;

		for(int j = 0; j <= sum / 2; j ++)
			for(int k = 0; k <= sum / 2; k ++)
			{
				if(!f[n][j][k]) continue;
				if(!istl(j, k, sum - j - k)) continue;
				ans = max(ans, helen(j, k, sum - j - k));
			}
		
	if(ans == -1) cout << ans << endl;
	else
	cout << (ll)(ans * 100) << endl;
}