牛客小白月赛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;
}

标签: 深度优先搜索

添加新评论