取数游戏：C++ 全排列解法

取数游戏：C++ 全排列解法

题目描述

给出一个 $n \times n$ 的矩阵，进行取数游戏。 取数共 $n$ 轮，第 $i$ 轮需要从每行分别取一个没取过的数字，设取出的数字总和是 $s$，则第 $i$ 轮的实际得分是 $i \times s$。 求 $n$ 轮取数的最大总得分。

输入格式

从标准输入读入数据。 第一行输入一个正整数 $n$（$n \le 100$）。 接下来 $n$ 行，每行输入 $n$ 个正整数 $a_{ij}$（$a_{ij} \le 10^6$），构成一个矩阵。

输出格式

输出到标准输出。 输出一个整数，表示最大总得分。

样例 #1

样例输入 #1

3
1 3 2
4 2 4
1 3 1

样例输出 #1

48

代码实现

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Matrix {
    int n;
    vector<vector<int>> data;
};

int main() {
    Matrix matrix;
    cin >> matrix.n;
    matrix.data.resize(matrix.n, vector<int>(matrix.n));
    for (int i = 0; i < matrix.n; ++i) {
        for (int j = 0; j < matrix.n; ++j) {
            cin >> matrix.data[i][j];
        }
    }

    vector<int> permutation(matrix.n);
    for (int i = 0; i < matrix.n; ++i) {
        permutation[i] = i;
    }

    int maxScore = 0;
    do {
        int score = 0;
        for (int i = 0; i < matrix.n; ++i) {
            score += (i + 1) * matrix.data[i][permutation[i]];
        }
        maxScore = max(maxScore, score);
    } while (next_permutation(permutation.begin(), permutation.end()));

    cout << maxScore << endl;
    return 0;
}

思路

由于数据范围比较小，可以直接使用暴力的全排列来枚举每一轮选取的数的方案。具体来说，可以使用 STL 中的 next_permutation 函数来生成所有的排列。

对于每一种排列，计算出对应的得分，取最大值即可。

时间复杂度为 $O(n!n)$，可以通过此题。