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

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

算法思路

为了获得最大总得分，我们可以采用贪心策略：

排序: 首先，将矩阵的每一行按照数字大小降序排序。这样可以保证每一行最大的数字优先被选中。
选取最大值: 在每一轮取数时，从每一行中选择当前最大且未被选取的数字。
记录选取: 为了避免重复选取，可以使用一个数组记录每一行已经被选取的数字的索引。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110;

struct node {
    int num, id;
};

node a[N][N];
int n;

bol cmp(node x, node y) {
    return x.num > y.num;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j].num);
            a[i][j].id = j;
        }
        sort(a[i] + 1, a[i] + n + 1, cmp);
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int maxn = 0;
        for (int j = 1; j <= n; j++) {
            if (a[j][i].num == 0) break;
            if (a[j][i].id > maxn) {
                maxn = a[j][i].id;
                ans += a[j][i].num * i;
            }
        }
    }
    cout << ans;
    return 0;
}

代码解释

struct node 用于存储矩阵中的每个数字及其索引，方便进行排序。
cmp 函数用于比较两个 node 对象的 num 值，实现降序排序。
循环遍历矩阵，将每一行的数字按照降序排序。
循环进行 'n' 轮取数，在每一轮中，遍历每一行，选择当前最大且未被选取的数字，并计算得分。
使用 maxn 变量记录当前行的最大索引，避免重复选取同一行的数字。

总结

通过贪心策略和排序操作，我们成功地实现了取数游戏的最大得分算法。代码简洁易懂，并使用 long long 数据类型防止整数溢出。希望本文能够帮助您更好地理解和解决类似的算法问题。