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

题目描述

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

思路

定义一个二维数组 $f(i,j)$ 表示取到第 $i$ 行，第 $j$ 列时的最大得分。
对于 $f(i,j)$，它可以从 $f(i-1,k)$ 转移而来，其中 $k$ 是指第 $i-1$ 行中没有被选过的列号。
转移方程：$f(i,j) = \max\limits_{k\in[1,n],k\ne j} {f(i-1,k) + i \times a_{i,j}}$。
最终答案为 $\max\limits_{j\in[1,n]}f(n,j)$。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 105;
int n, a[MAXN][MAXN], f[MAXN][MAXN];

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

    // 初始化第一行
    for (int j = 1; j <= n; ++j) {
        f[1][j] = a[1][j];
    }

    // 动态规划
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= n; ++k) {
                if (k != j) {
                    f[i][j] = max(f[i][j], f[i - 1][k] + i * a[i][j]);
                }
            }
        }
    }

    // 求解最大得分
    int ans = 0;
    for (int j = 1; j <= n; ++j) {
        ans = max(ans, f[n][j]);
    }

    cout << ans << endl;
    return 0;
}

时间复杂度

时间复杂度：$O(n^3)$。