取数游戏：动态规划求解最大得分

题目描述

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

样例输出 #1

C++ 代码实现

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

using namespace std;

const int N = 110;

int n;
int w[N][N];
int f[N][N];

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

    memset(f, -0x3f, sizeof f);
    f[1][1] = 0; // 初始化第一轮得分
    for (int i = 2; i <= n + n; i ++ )
        for (int a = 1; a <= n; a ++ )
        {
            int b = i - a;
            if (b < 1 || b > n) continue;

            for (int c = 1; c < a; c ++ )
                for (int d = 1; d < b; d ++ )
                    f[a][b] = max(f[a][b], f[c][d] + w[a][i - a] + w[b][i - b] + (i - 1) * w[c][d]);

            if (a == b) f[a][b] -= w[a][i - a]; // 避免重复计算对角线元素
        }

    cout << f[n][n] << endl;

    return 0;
}

代码解释：

状态定义：
- f[a][b] 表示前 a 行和 b 列取数的最大得分。
状态转移方程：
- 当 a 和 b 不相等时，考虑当前轮取数的情况：
  - 从第 a 行取 w[a][i - a]，从第 b 行取 w[b][i - b]。
  - 前 a - 1 行和 b - 1 列的最大得分是 f[c][d]，其中 c < a，d < b。
  - 当前轮得分是 i * (w[a][i - a] + w[b][i - b])。
  - 状态转移方程：f[a][b] = max(f[a][b], f[c][d] + w[a][i - a] + w[b][i - b] + (i - 1) * w[c][d])。
- 当 a 和 b 相等时，表示当前轮取的是对角线元素，需要减去重复计算的得分。
  - 状态转移方程：f[a][b] -= w[a][i - a]。
边界条件：
- f[1][1] = 0，表示第一轮取数的得分是 0。
最终结果：
- f[n][n] 表示 $n$ 轮取数的最大总得分。

关键点：

代码中 i 的循环范围是 2 到 n + n，这是因为 i 表示当前取数的轮数，所以最大值是 n + n。
代码中 c 和 d 的循环范围是 1 到 a - 1 和 1 到 b - 1，这是因为要考虑前 a - 1 行和 b - 1 列的所有取数情况。
代码中 f[a][b] -= w[a][i - a] 这一行代码是用来避免重复计算对角线元素的得分的。

希望这能够帮助你理解这道题的解题思路和 C++ 代码实现。