题解 | #小白月赛43 C.木棍游戏#

C.木棍游戏 木棍游戏
爆搜题目，赛时没写出来呜呜呜呜

知识点：搜索，海伦公式

海伦公式求面积：
	h = (周长)/2
   	面积s = sqrt(h*(h-a)*(h-b)*(h-c))

不用sort呜呜呜呜，另外记得变量都设为double,int被卡了呜呜
我们可以把三角形三条边设为l1,l2,l3,然后分别枚举每根木棍分别放三边的情况即可。 详情见代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 10;
double a[N];
int n;
double mx = -1e9;
double calc(double a,double b,double c)
{
    double h = (a+b+c)/2;
    double s = sqrt(h*(h-a)*(h-b)*(h-c));
    return s;
}
//cnt记录的是当前枚举的第几根木棍
double dfs(int l1,int l2,int l3,int cnt)
{
    if(cnt>n) return -1;//最优性剪枝？？
    if(l1+l2>l3&&l1+l3>l2&&l2+l3>l1)
    {//如果是三角形才计算面积
        mx = max(mx,calc(l1,l2,l3));
    }
  	//爆搜所有情况
    dfs(l1+a[cnt],l2,l3,cnt+1);
    dfs(l1,l2+a[cnt],l3,cnt+1);
    dfs(l1,l2,l3+a[cnt],cnt+1);
    dfs(l1,l2,l3,cnt+1);
    return mx;
}
int main()
{
    cin>>n;
    for(int i = 0;i<n;i++)
    {
        cin>>a[i];
    }
    double l1 = 0,l2 = 0,l3 = 0;
    double ans = dfs(l1,l2,l3,0);
    if(fabs(ans+1e9)<1e-9)//也可以ans<=0来判断....
    {
        cout<<"-1";
        return 0;
    }
    printf("%.1f",ans);
}