大前端

前端学习之家-大前端

【DP周】- 第一周(基础DP) - day5 - 三角形牧场

三角形牧场
在这里插入图片描述
首先分析题目
要计算三角形面积,给的条件有边
肯定要想到海伦公式

p = ( a + b + c ) / 2 p=(a+b+c)/2 p=(a+b+c)/2
S = p ∗ ( p − a ) ∗ ( p − b ) ∗ ( p − c ) S=\sqrt{p*(p-a)*(p-b)*(p-c)} S=p(pa)(pb)(pc)

然后分析状态
每个木板存在三种状态
1.在第一条边上
2.在第二条边上
3.在第三条边上
这三个状态直接决定了这三条边能不能构成三角形
那么就可以列出状态转移
f[i][j][k][l]表示前i条木板,三条边分别为在i,j,k时是否可以构成三角形
然后问题来了
发现 40 ∗ 800 ∗ 800 ∗ 800 40*800*800*800 40800800800数组肯定开不了那么大(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;
}

发表评论:

Copyright Your WebSite.Some Rights Reserved.