取数游戏

题目描述

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

输入格式

从标准输入读入数据。 第一行输入一个正整数 'n'（'n ≤ 100'）。 接下来 'n' 行，每行输入 'n' 个正整数 'a_ij'（'a_ij ≤ 10⁶'），构成一个矩阵。

输出格式

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

样例 #1

样例输入 #1

3
1 3 2
4 2 4
1 3 1

样例输出 #1

48

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int w[N][N];
bool st[N];
int score;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> w[i][j];

    for (int i = 1; i <= n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || w[i][j] > w[i][t]))
                t = j;

        st[t] = true;
        score += i * w[i][t];
    }

    cout << score << endl;

    return 0;
}