CF431B题解

· · 题解

思路分析

答题思路

一道纯暴力题！

因为我们发现数据最大是 5，而枚举全排列的时间复杂度为 \mathcal O(n!)，对于这种极小的数据范围是丝毫不用顾虑的，因为我们只需要执行 120 次。

如何快速求出一个数组的全排列？

我们可以使用 dfs，一层一层获取这个数组的全排列。

是 STL 大法可是 C++ 党的福利，不用白不用。

在 STL 中，有一个函数 next_permutation()，可以枚举一个数组的全排列，但是时间复杂度高达 O(n!)，在 1 秒内最多只能枚举长度为 11 的数组的全排列。

因为这次最大的长度为 5，所以是不会超时的。

敲响警钟：一开始的数组必须是升序排列的，否则程序运行结果就会出现问题！

更多了解见这里。

如何计算一种方法的幸福度？

我们只需按照题目进行模拟即可，题目中已经有明显的示例了，这里不再多言。

复杂度分析

next_permutation() 的时间复杂度是 \mathcal O(n!)，计算幸福度的时间复杂度是 O(1) 的，所以最终的时间复杂度是 \mathcal O(n!) 的。

程序实现

#include <bits/stdc++.h>
using namespace std;
int ans = INT_MIN, g[6][6], a[6] = {0, 1, 2, 3, 4, 5}; // ans要赋很小的值，才能求出最大值！
int main() {
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++)
            cin >> g[i][j]; // 读入
    do ans = max(ans, g[a[1]][a[2]] + g[a[2]][a[1]] + g[a[2]][a[3]] + g[a[3]][a[2]] + 2 * g[a[3]][a[4]] +
                     2 * g[a[4]][a[3]] + 2 * g[a[4]][a[5]] + 2 * g[a[5]][a[4]]);
// 计算幸福度，只需模拟题意
    while (next_permutation(a + 1, a + 6)); // 枚举全排列，后面一项本为a+5+1，简写为a+6
    cout << ans;
    return 0;
}