注意

  该博客是为了帮助同学学习，并非为了协助同学刷题，请读者保持自觉，请勿做CV工具人。另外为了节省篇幅，代码中不再写明#include，如果遇到我没有声明的函数，那么就是某一个头文件中的函数，读者搜索“c + 函数名字”就能查到相关信息。

题目

  点击查看原题

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

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

输入描述

第一行包含一个整数n（3 ≤ n ≤ 8），表示木棍的数量。
第二行包含n个整数，用空格隔开，表示n根木棍的分别长度a1，a2……an。其中 1 ≤ ai ≤ 1e3。

输出描述

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

样例

1
2
3
4
5
6
输入：
3
3 4 5
-------------
输出：
6.0
1
2
3
4
5
6
输入：
3
3 4 7
-------------
输出：
-1

思路与代码解析

  首先声明，这道题的“正确”思路应该是使用DFS，我这是剑走偏锋各位千万不要学。

  拿到题以看，哈，这不是排列组合吗。再仔细以看，哟，输入范围这么小。打表打表，都可以打表！

  随后，我便这么打了个表出来：

1
2
3
4
5
6
7
8
const vector<int> indexMap[] {
    vector<int[2]> {{1, 1}},
    vector<int[2]> {{1, 1}},
    vector<int[2]> {{1, 1}, {1, 2}},
    vector<int[2]> {{1, 1}, {1, 2}},
    vector<int[2]> {{1, 1}, {1, 2}, {1, 3}, {2, 2}}},
    vector<int[2]> {{1, 1}, {1, 2}, {1, 3}, {2, 2}}
};

  先不说这个表是否正确，先来说一说为什么这么打表。三角形有三条边，那么我们要做的肯定是把输入数据分成三份，这个表存的就是在指定数量下这三份前两份应该分多少。indexMap[0]表示的就是当木棍数量为3时的分配策略，indexMap[1]表示的就是木棍数量为4时的分配策略，以此类推。

  省略第三份想必都能理解，第三份可以直接推算出来，就没必要打了。

  随后就出现了一个严重的问题，这段代码无法编译。为什么无法编译呢？其实就是我误以为vector有一个带有变长参数的构造函数。知道错误之后再修改带代码，就变成了这样子（中间发现漏了情况又补充进去了）：

1
2
3
4
5
6
7
8
9
vector<vector<int>> indexMap[6];

void init() {
    for (auto& item: indexMap) item.push_back({1, 1});
    for (int i = 2; i != 6; ++i) indexMap[i].push_back({1, 2});
    for (int i = 3; i != 6; ++i) indexMap[i].push_back({2, 2});
    for (int i = 4; i != 6; ++i) indexMap[i].push_back({1, 3});
    indexMap[5].push_back({2, 3});
}

  表打好了，现在继续来说我们的解题思路。首先，我们需要有两个函数用来判断是否是三角形以及计算三角形面积；然后我们需要写一个函数用来枚举从长度为length的数组中取N个数的所有可能。

  这样说来急需编写的有三个函数：

  1. bool check(int a, int b, int c)
  2. double calculate(int a, int b, int c)
  3. void select(?)

  前两个非常好编写，最后一个函数是整个代码中的难点，如何才能把所有的可能枚举一遍？并且要尽可能地避免重复（可以不避免，但是重复少的话性能会更优）。

  我们以从五个数中选两个为例，如果我们用脑子枚举所有情况我们会怎么办？至少我的思路是这样的：

五选二

  那么从五个数里面选三个怎么选呢？同理，我们增加指针的数量就可以了：

五选三

  现在我们找出规律了，我们把指针从右往左编号为：1, 2, …, n。先移动1号指针，直到不能继续向右移动；此时把2号指针向右移动一格，并把1号指针放置在2号指针右边，继续移动1号指针；以此往复，便可以不重复的枚举所有情况。

  确定了思路就可以继续写代码了，这么看来我们还需要先编写一个函数，用来移动“指针”：

1
2
3
4
5
6
7
8
bool move(vector<int>& record, int index, int length) {
    if (index == -1) return false;
    int maxIndex = int(length - (record.size() - index - 1));
    if (++record[index] != maxIndex) return true;
    if (!move(record, index - 1, length)) return false;
    record[index] = record[index - 1] + 1;
    return true;
}

  因为这道题题目限制，指针数量一定不超过2，所以不需要考虑堆栈溢出的问题，指针数量多的话就必须用循环写了。接着来解释一下这里面的东西都是什么：

  函数的返回值用来标明是否创造出了一个新的可用的指针序列，如果所有指针都移动到了最右端，那么将无法继续产生新的可用序列。

  record存的是当前各个指针指向的下标，而record的下标对应的就是指针的编号。这里需要强调的是，虽然上文我们举例子的时候指针是从右往左以1为起始编号的，但是这里是从左往右以0为起始编号的，这个一定要分清楚。同时record的大小也指明了需要取几个数。

  index，顾名思义，存的就是当前正在移动的指针的编号。

  length存的就是一共有几个数，至于为什么没有用全局变量存length，这个后面就能明白了。

  maxIndex用来标明当前指针能够移动到的最右端（不包含）在哪里。

  现在，我们可以轻松的编写出select函数了：

1
2
3
4
5
6
7
void select(int amount, int length, const function<void(vector<int>&)>& fun) {
    vector<int> record(amount);
    for (int i = 0; i != amount; ++i) record[i] = i;
    do {
        fun(record);
    } while (move(record, amount - 1, length));
}

  同样，我们解释一下这个函数的组成：

  amount用来指示需要取几个数字。

  length用来指示一共有多少个数字。

  fun可以理解为存储了一个函数指针，目标函数接收一个vector<int>&参数，这个传入的vector存储的是当前的指针序列，每产生一个新的序列就会调用一次该函数。

  可以发现，select函数的运行和要进行取数的数组没有任何关系，它只与有几个数和要取几个数有关。

  现在再考虑具体应用。假如我们需要分两次取数，我们需要考虑两次取数时指针序列的起始位置，这个位置很难快速地想象出来如何计算，很容易出现大面积重复计算或缺东少西的情况。

  所以我们采用另一种取数方式来解决这个问题。即一次取出两次要取的数量，然后再从取出的数中取出一部分，这样就可以看成是两次取数的结果了：

  这时，我们发现，我们前面打的表还可以继续优化，因为我们使用到的量其实是两次取数的数量之和与其中一次取数的数量。所以我们可以把表转化为下面这种形式，这样就减少了代码的计算量：

1
2
3
4
5
6
7
8
9
vector<pair<int, int>> indexMap[6];

void init() {
    for (auto& item: indexMap) item.emplace_back(2, 1);
    for (int i = 2; i != 6; ++i) indexMap[i].emplace_back(3, 1);
    for (int i = 3; i != 6; ++i) indexMap[i].emplace_back(4, 2);
    for (int i = 4; i != 6; ++i) indexMap[i].emplace_back(4, 1);
    indexMap[5].emplace_back(5, 2);
}

  到这里，所有东西都清晰了，只需要补出其余的代码即可。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
vector<pair<int, int>> indexMap[6];
int gInput[8];
int gLength = 0;

void init() {
    for (auto& item: indexMap) item.emplace_back(2, 1);
    for (int i = 2; i != 6; ++i) indexMap[i].emplace_back(3, 1);
    for (int i = 3; i != 6; ++i) indexMap[i].emplace_back(4, 2);
    for (int i = 4; i != 6; ++i) indexMap[i].emplace_back(4, 1);
    indexMap[5].emplace_back(5, 2);
}

bool move(vector<int>& record, int index, int length) {
    if (index == -1) return false;
    int maxIndex = int(length - (record.size() - index - 1));
    if (++record[index] != maxIndex) return true;
    if (!move(record, index - 1, length)) return false;
    record[index] = record[index - 1] + 1;
    return true;
}

void select(int amount, int length, const function<void(vector<int>&)>& fun) {
    vector<int> record(amount);
    for (int i = 0; i != amount; ++i) record[i] = i;
    do {
        fun(record);
    } while (move(record, amount - 1, length));
}

bool check(int a, int b, int c) {
    return (a + b > c) && (a + c > b) && (b + c) > a;
}

double calculate(int a, int b, int c) {
    double p = (a + b + c) / 2.0;
    return sqrt(p * (p - a) * (p - b) * (p - c));
}

double ans = 0;

void forEachMap(vector<pair<int, int>>& map, vector<int>& list, int length) {
    int sum = 0;
    for (const auto& item: list) sum += gInput[item];
    for (const auto& item: map) {
        select(item.first, length, [&](const vector<int>& selected) {
            int allSum = 0;
            for (const auto& index: selected) allSum += gInput[list[index]];
            select(item.second, int(selected.size()), [&](const vector<int>& inner) {
                int a = 0;
                for (const auto& index: inner) a += gInput[list[selected[index]]];
                int b = allSum - a;
                int c = sum - allSum;
                if (check(a, b, c)) ans = max(ans, calculate(a, b, c));
            });
        });
    }
}

void forEachFrequency() {
    for (int amount = 3; amount <= gLength; ++amount) {
        select(amount, gLength, [amount](vector<int>& list) {
            auto& map = indexMap[amount - 3];
            forEachMap(indexMap[amount - 3], list, amount);
        });
    }
}

int main() {
    init();
    cin >> gLength;
    for (int i = 0; i != gLength; ++i) cin >> gInput[i];
    forEachFrequency();
    if (ans < 1e-6) printf("-1");
    else printf("%.1f", ans);
    return 0;
}
创作不易，扫描下方打赏二维码支持一下吧ヾ(≧▽≦*)o