取数游戏：动态规划、贪心算法详解与C++代码实现

题目描述

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

算法1

(动态规划) $O(n^3)$

设 $f_{i,j,k}$ 表示第 $1$ 到第 $i$ 轮，第 $1$ 到第 $j$ 行已经取过 $k$ 个数的最大得分。

状态转移方程：

$$f_{i,j,k} = \max{f_{i-1,j-1,t} + i \times s_{j,k}}$$

其中 $s_{j,k}$ 表示第 $j$ 行第 $k$ 个数，$t \in [0, k-1]$。

时间复杂度

状态数 $O(n^3)$，状态转移 $O(n)$，总时间复杂度 $O(n^4)$。

空间复杂度

$O(n^3)$。

C++ 代码

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

const int MAXN = 105;
int n, a[MAXN][MAXN], f[MAXN][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 i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= j; k++) {
                for (int t = 0; t < k; t++) {
                    f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][t] + i * a[j][k]);
                }
            }
        }
    }
    cout << f[n][n][n] << endl;
    return 0;
}

算法2

(贪心) $O(n^3)$

对于每一行，我们在取数的时候，优先选取当前行中最大的数。

时间复杂度

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

空间复杂度

$O(n^2)$。

C++ 代码

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

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

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            sum[i][j] = sum[i][j - 1] + a[i][j];
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int max_val = 0, max_idx = 0;
            for (int k = j; k <= n; k++) {
                if (a[k][j] > max_val) {
                    max_val = a[k][j];
                    max_idx = k;
                }
            }
            ans += i * (sum[max_idx][n] - sum[max_idx][j - 1]);
            for (int k = max_idx; k > j; k--) {
                for (int l = 1; l <= n; l++) {
                    a[k][l] = a[k - 1][l];
                }
            }
            for (int k = j; k <= n; k++) {
                sum[k][n] = sum[k][n - 1] + a[k][n];
            }
        }
    }
    cout << ans << endl;
    return 0;
}

算法3

(贪心) $O(n^2)$

对于每一行，我们在取数的时候，优先选取当前行中最大的数。我们每次取完一个数之后，就可以将这个数所在的行和列删除，因为这个数已经被取走了，而在后续的取数过程中，这一行和这一列中的数都不能再被取走了。

时间复杂度

总时间复杂度 $O(n^2)$。

空间复杂度

$O(n^2)$。

C++ 代码

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

const int MAXN = 105;
int n, a[MAXN][MAXN];
bool row[MAXN], col[MAXN];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int max_val = 0, max_row = 0, max_col = 0;
        for (int j = 1; j <= n; j++) {
            if (!row[j] && !col[j] && a[j][j] > max_val) {
                max_val = a[j][j];
                max_row = j;
                max_col = j;
            }
        }
        ans += i * max_val;
        row[max_row] = true;
        col[max_col] = true;
    }
    cout << ans << endl;
    return 0;
}