取数游戏 - C++ 代码实现及优化

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

C++ 代码

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

using namespace std;

const int N = 110;

int n;
int w[N][N], used[N][N];
long long f[N][N];

struct Node {
    int x, y;
    long long v;
    bool operator < (const Node &t) const {
        return v > t.v;
    }
} q[N * N];

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++)
        for (int j = 1; j <= n; j++)
            q[(i - 1) * n + j] = {i, j, w[i][j]};

    sort(q + 1, q + n * n + 1);

    for (int i = 1; i <= n * n; i++) {
        int x = q[i].x, y = q[i].y;
        f[x][y] = q[i].v * (x + y - 1);
        for (int j = 1; j <= n; j++)
            if (used[x][j] && used[j][y])
                f[x][y] = max(f[x][y], f[j][y] + q[i].v * (x + y - j - 1));
        used[x][y] = true;
    }

    long long res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            res = max(res, f[i][j]);

    cout << res << endl;

    return 0;
}

代码解释

使用 struct Node 结构体存储矩阵元素的坐标和值，并重载 < 运算符，方便排序。
使用 sort 函数对结构体数组进行排序，将矩阵元素按值从大到小排序。
使用二维数组 f[N][N] 进行动态规划，f[i][j] 表示从矩阵第 'i' 行第 'j' 列元素开始进行取数，所能得到的最大得分。
遍历排序后的结构体数组，对于每个元素，计算当前元素的得分，并与之前的状态进行比较，更新 f[i][j] 的值。
使用二维数组 used[N][N] 记录每个元素是否已经被取过。
最后遍历 f[N][N] 数组，找到最大得分，并输出。

优化点

使用 long long 类型进行计算，以保证结果的准确性。
使用 sort 函数对结构体数组进行排序，避免手动排序，提高效率。
使用动态规划，避免重复计算，提高效率。

总结

本文提供了一个C++代码实现，用于解决取数游戏问题。代码采用了结构体、排序和动态规划等技巧，并使用 long long 类型进行计算，以保证结果的准确性。该代码可供参考，并可根据需要进行进一步的优化。