牛客小白月赛43

C - 木棍游戏

https://ac.nowcoder.com/acm/contest/11220/C

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

给出 $n$ 根长度不一的木棍，第 $i$ 根棍子长度为 $a_i$ 。两根长度分别为 $a_b$ 和 $a_c$ 的木棍可以拼接成一根长度为 $a_b+a_c$ 的木棍，同理 $3$ 根， $4$ 根，甚至 $n$ 根都能拼接。

问：使用这 $n$ 根木棍作三角形的边（一根木棍至多使用一次，也可以不使用），能拼出的面积最大的三角形的面积。

输入描述:

第一行包含一个整数 $n$ $(3 \le n \le 8)$，表示木棍的数量。
第二行包含 $n$ 个整数，用空格隔开，表示 $n$ 根木棍的分别长度 $a_1,a_2,...,a_n$ 其中 $1\le a_i\le 1e3$。

输出描述:

输出一行，表示能拼出来的最大三角形的面积，结果保留一位小数。如果无法拼出三角形，输出$-1$。

示例1

输入

3
3 4 5

输出

6.0

示例2

输入

3
3 4 7

输出

-1

我的笔记

分析

木棍数量最大为 8，每个木棍有 4 个状态：不用、边 a、边 b、边 c，如果将每个状态全部枚举，时间复杂度为 $O(4^n)$，最大 $4^8=65536$，时间复杂度在合理范围内，因此直接搜索一遍所有情况。

使用 DFS，枚举每种情况，到达目标时，计算出对应的边 a、边 b、边 c，使用海伦公式，若根号下是正数，即这个三角形成立，若是负数，则无法构成三角形。

答案初值设置为 0，每次求出答案保留最大值，最后若答案为 0，则无法构成，若答案非 0，则输出答案。

源码

#include <bits/stdc++.h>

using namespace std;

int n, length[8], choice[8];
bool flag[8];
double ans = 0;

void dfs(int x)
{
    if (x == n)
    {
        int a = 0, b = 0, c = 0;
        for (int i = 0; i < n; i++)
        {
            if (choice[i] == 0)
            {
                continue;
            }
            else if (choice[i] == 1)
            {
                a += length[i];
            }
            else if (choice[i] == 2)
            {
                b += length[i];
            }
            else if (choice[i] == 3)
            {
                c += length[i];
            }
        }
        double p = 1.0 * (a + b + c) / 2;
        double spow2 = p * (p - a) * (p - b) * (p - c);
        if (spow2 > 0)
            ans = max(ans, sqrt(spow2));
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        if (!flag[x])
        {
            flag[x] = true;
            choice[x] = i;
            dfs(x + 1);
            flag[x] = false;
        }
    }
}

int main(void)
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> length[i];
    }
    dfs(0);
    if (ans != 0)
        printf("%.1lf\n", ans);
    else
        printf("-1\n");
    return 0;
}