取数游戏算法实现：最大化得分策略

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

3
1 3 2
4 2 4
1 3 1

样例输出 #1

48

C++ 代码实现

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
int n, a[N][N], b[N];
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            cin >> a[i][j];
    long long res = 0;
    for(int i = 1; i <= n; i ++)
    {
        int mx = -1;
        for(int j = 1; j <= n; j ++)
            if(!b[j] && (mx == -1 || a[i][j] > a[i][mx]))
                mx = j;
        b[mx] = 1;
        res += i * a[i][mx];
    }
    cout << res << endl;
    return 0;
}

更简便的代码优化方案

核心思想: 每一轮选择当前行中最大的未被选取的数字，可以保证最大化得分。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
int n, a[N][N];
bool vis[N]; // 记录每一列是否已被选择
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];

    long long res = 0;
    for (int i = 1; i <= n; i++)
    {
        int maxVal = 0, maxCol = 0; // 存储当前行最大值和对应列号
        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && a[i][j] > maxVal)
            {
                maxVal = a[i][j];
                maxCol = j;
            }
        }
        res += i * maxVal; // 计算当前轮得分
        vis[maxCol] = true; // 标记当前列已被选择
    }
    cout << res << endl;
    return 0;
}

代码优化说明:

1. 使用 vis 数组记录每一列是否已被选择，避免了使用 b 数组遍历所有列，提升了效率。
2. 使用 maxVal 和 maxCol 变量存储当前行最大值和对应列号，避免了重复遍历寻找最大值，提高了代码可读性。

总结:

本文介绍了用 C++ 代码解决一个取数游戏的算法问题，通过贪心策略最大化得分。文章还提供了更简便的代码优化方案，提升代码效率和可读性。