取数游戏 - 动态规划解法 - 常规

取数游戏 - 动态规划解法

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

代码思路

这道题可以使用动态规划来解决。定义一个二维数组 dp，其中 dp[i][j] 表示在第 i 轮取数时，选择第 i 行的第 j 列数字时的最大得分。则有状态转移方程：dp[i][j] = max(dp[i][j], dp[i-1][k] + i * a[i][j])，其中 k 表示在第 i-1 轮中选择的列数。

最终的最大得分就是 dp[n][j] 中的最大值。

代码实现

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

struct st {
    int val, idx;
};

bool cmp(st a, st b) {
    return a.val > b.val;
}

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

    vector<vector<long long>> dp(n + 1, vector<long long>(n, 0));
    for (int i = 1; i <= n; i++) {
        vector<st> temp;
        for (int j = 0; j < n; j++) {
            temp.push_back({a[i-1][j], j});
        }
        sort(temp.begin(), temp.end(), cmp);

        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (k == j) continue;
                dp[i][j] = max(dp[i][j], dp[i-1][k] + i * a[i-1][j]);
            }
        }
    }

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[n][i]);
    }
    cout << ans << endl;

    return 0;
}

复杂度分析

该算法使用了一个二维数组 dp，其大小为 $n\times n$，所以空间复杂度为 $O(n^2)$。在计算 dp 数组的过程中，需要进行两层嵌套循环，所以时间复杂度为 $O(n^2)$。因此，总的时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。