题解 | #木棍游戏#

这道题我第一反应是用贪心去写，无奈贪了半天都没有贪出来，所以只能用dfs暴力过题

数学知识：海伦公式链接：https://baike.baidu.com/item/%E6%B5%B7%E4%BC%A6%E5%85%AC%E5%BC%8F/106956

思路就是dfs每个面积暴力比对，选出最大的就行

注：呜呜呜，在那个不加边的情况上debug了好久

#include<cmath>
#include<algorithm>
using namespace std;
const int N=10;

int n;
int f[N];
float res=-1;
float S(int a,int b,int c)//海伦公式
{
    float p=(a+b+c)/2.0;
    return sqrt(p*(p-a)*(p-b)*(p-c));
}
void dfs(int a,int b,int c,int u)
{
    if(u>n)return;
    if(a+b>c&&a+c>b&&b+c>a)
        res=max(res,S(a,b,c));
    
    dfs(a+f[u],b,c,u+1);//第一条边加上现有的边
    dfs(a,b+f[u],c,u+1);//第二条边加上现有的边
    dfs(a,b,c+f[u],u+1);//第三条边加上现有的边
    dfs(a,b,c,u+1);//不加，有可能加了还小了，也可能加了不合法了
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&f[i]);
    
    dfs(0,0,0,0);
    printf("%.1f",res);
    return 0;
}