木棍游戏

海伦公式：

当时其实是有想到海伦公式的，但没注意到n的最大值，感觉怎样都会超时，以及dfs不熟练，只拿来解过迷宫，导致完全没有思路。。。

#include<bits/stdc++.h>
using namespace std;

int n;
double a[10];
double maxx =-1;

//海伦公式
double helen(double a,double b,double c){
    double p = (a+b+c)/2;
    double s = sqrt(p*(p-a)*(p-b)*(p-c));
    return s;
}

//x，y，z为用于木棍分组，cnt从0到n代表每一根木棍
void dfs(int x,int y,int z,int cnt){
	double res;
    if(cnt>n)return;
    if(x+y>z&&x+z>y&&y+z>x){
    	res=helen(x,y,z);
        if(res>maxx)maxx=res;
    }
    
    //把每根木棍依次放入每组或者都不放入，枚举所有情况
    dfs(x+a[cnt],y,z,cnt+1);
    dfs(x,y+a[cnt],z,cnt+1);
    dfs(x,y,z+a[cnt],cnt+1);
    dfs(x,y,z,cnt+1);
}

int main(){
    cin>>n;
    for(int i = 0;i<n;i++)cin>>a[i];
	dfs(0,0,0,0);
    printf("%.1f",maxx);
    return 0;
}

以上