取数游戏 - 贪心算法求解最大总得分

取数游戏 - 贪心算法求解最大总得分

题目描述

给出一个 $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

算法

(贪心)

首先考虑一种贪心的策略：每一轮都选择每一行中的最大值，这种策略的正确性可以通过反证法证明。

假设当前是第 $i$ 轮，第 $j$ 行已经选出了数 $a_{j,k}$，那么在后面的轮次中，第 $j$ 行的贡献一定不会超过 $i \times a_{j,k}$。如果后面的轮次中，我们选择了第 $j$ 行中的另一个数 $a_{j,l}$，且 $l \neq k$，那么第 $j$ 行的贡献就是 $(i+1) \times a_{j,l}$，如果 $a_{j,l} > a_{j,k}$，那么第 $j$ 行的贡献就会超过 $i \times a_{j,k}$，这与我们的假设矛盾。因此我们可以得出结论：在每一轮中，选择每一行中的最大值可以得到最优解。

时间复杂度

总共需要遍历 $n$ 行，每行需要找到最大值，时间复杂度是 $O(n^2)$。

C++ 代码

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

int main() {
    int n;
    cin >> n;
    int a[101][101];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int maxVal = 0;
        for (int j = 1; j <= n; j++) {
            maxVal = max(maxVal, a[j][i]);
        }
        ans += (long long) i * maxVal;
    }
    cout << ans << endl;
    return 0;
}