取数游戏：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 <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int n;
int a[N][N], f[N][N], g[N][N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    memset(f, -0x3f, sizeof f);
    f[1][1] = a[1][1];
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++) {
            int k = i - j + 1;
            g[j][k] = max(g[j - 1][k], g[j][k - 1]) + a[j][k];
            if (j < i) f[i][j] = max(f[i][j], f[i - 1][j] + i * g[j][k]);
            if (k > 1) f[i][j] = max(f[i][j], f[i - 1][j - 1] + i * g[j][k]);
        }
    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
    cout << res << endl;
    return 0;
}

代码说明：

使用二维数组 'f[i][j]' 表示前 'i' 轮，第 'i' 轮从第 'j' 行取数的最大得分。
使用二维数组 'g[i][j]' 表示从第 'i' 行开始，到第 'i + j - 1' 行，取数的最大总和。
代码利用动态规划的思想，通过枚举第 'i' 轮取数的起点，计算 'f[i][j]' 的最大值。
'g[i][j]' 的计算利用了前一轮的取数信息，递归地计算得到。
最后，通过遍历 'f[n][i]'，找到 'n' 轮取数的最大总得分。