题解 | #木棍游戏#

Problem

Solution

首先看到数据范围很小，小于等于8，第一反应就是可以用暴搜来做，依次枚举每种情况，取最大值即可得到答案。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int N = 10;
int q[N];
double res;
int n;
bool st[N];


double ju(double a, double b, double c)  // 求三角形面积
{
    double p = (a + b + c) / 2;
    double s = sqrt(p * (p - a) * (p - b) * (p - c));
    return s;
}

void dfs(int a, int b, int c, int index)  // 枚举每种情况
{
    if (a + b > c && a + c > b && b + c > a)
    {
        res = max(res, ju(a, b, c));
    }
    
    for (int i = index; i <= n; i++)
    {
        if (!st[i])
        {
            st[i] = true;
            dfs(a + q[i], b, c, index + 1);  // 分别加到三条边上
            dfs(a, b + q[i], c, index + 1);
            dfs(a, b, c + q[i], index + 1);
            st[i] = false;
            dfs(a, b, c, index + 1);  // 都不加
        }
        
    }
}



int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> q[i];
    
    dfs(0, 0, 0, 1);
    
    if (res > 0) printf("%.1lf", res);
    else cout << -1;
    
    return 0;
}