题解 | #木棍游戏#
木棍游戏
https://ac.nowcoder.com/acm/contest/11220/C
题意: 给出一些互不相同的木棍，选择其中的一些木棍。问能够拼凑出的三角形中最大的面积是多少。若不能拼出任何三角形，输出 。
制约:
前置知识：三斜求积（海伦公式）。
- 数据较小，直接暴搜。
CPP代码
#include <bits/stdc++.h>
using namespace std;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n;
std::cin >> n;
std::vector<int> A(n);
for (auto &i : A) {
std::cin >> i;
}
double ans = 0.0;
std::function<void(int, int, int, int)> DFS =
[&](int a, int b, int c, int id) {
if (a && b && c && a + b > c && a + c > b && b + c > a) {
double p = a + b + c;
p /= 2.;
ans = std::max(ans, std::sqrt(p * (p - a) * (p - b) * (p - c)));
}
if (id > n) {
return;
}
DFS(a, b, c + A[id], id + 1);
DFS(a + A[id], b, c, id + 1);
DFS(a, b + A[id], c, id + 1);
DFS(a, b, c, id + 1);
};
DFS(0, 0, 0, 0);
if (ans == 0) {
std::cout << -1;
} else {
std::cout << std::fixed << std::setprecision(1) << ans;
}
return 0 ^ 0;
}
bonus: 如果需要使用全部的木棍，该怎么处理？ 去洛谷看看这个题目
查看3道真题和解析
