取数游戏 - 贪心算法解题

取数游戏 - 贪心算法解题

题目描述

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

输入格式

从标准输入读入数据。 第一行输入一个正整数 'n' ('n≤100')。 接下来 'n' 行，每行输入 'n' 个正整数 'a_{ij}' ('a_{ij}≤10^6')，构成一个矩阵。

输出格式

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

样例 #1

样例输入 #1

3
1 3 2
4 2 4
1 3 1

样例输出 #1

48

Solution

本题可以使用贪心算法解决。每次选择每行中最大的数。

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 max_val = 0;
    for (int j = 1; j <= n; ++j) {
      max_val = max(max_val, a[j][i]);
    }
    ans += i * max_val;
  }
  cout << ans << endl;
  return 0;
}