取数游戏：最大得分算法及 C++ 代码实现

题目描述

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

输入格式

从标准输入读入数据。第一行输入一个正整数 'n' ('n <= 100')。接下来 'n' 行，每行输入 'n' 个正整数 'a[i][j]' ('a[i][j] <= 10^6')，构成一个矩阵。

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

算法：贪心

每一轮在所有可选的数字中选择最大的数字。
选完一个数字之后，将这一行和这一列中的所有数字标记为不可选。

时间复杂度：O(n^3)

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 100;
int n, a[MAXN][MAXN], vis[MAXN][MAXN];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }

    long long ans = 0;
    for (int k = 1; k <= n; k++) {
        int max_val = 0, row = -1, col = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!vis[i][j] && a[i][j] > max_val) {
                    max_val = a[i][j];
                    row = i;
                    col = j;
                }
            }
        }
        ans += k * max_val;
        vis[row][col] = 1;
        for (int j = 0; j < n; j++) {
            vis[row][j] = 1;
        }
        for (int i = 0; i < n; i++) {
            vis[i][col] = 1;
        }
    }

    cout << ans << endl;
    return 0;
}