取数游戏：动态规划解法

题目描述

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

解题思路

由于题目要求每一行都要取一个数，因此我们可以考虑对每一行的数字进行排序，然后每次取最大的数字。具体地，我们可以将每一行的数字放入一个小根堆中，每次取出堆顶元素，同时将该元素所在行的下一个元素放入堆中。

C++ 代码

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

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];
        }
        sort(a[i].begin(), a[i].end(), greater<int>()); // 对每一行进行降序排序
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 小根堆，存储 (数字, 行号)
    for (int i = 0; i < n; ++i) {
        pq.push({a[i][0], i}); // 将每一行的第一个数字放入堆中
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) { // 进行 n 轮取数
        auto [val, row] = pq.top(); // 取出堆顶元素
        pq.pop();
        ans += i * val;
        if (row + 1 < n) { // 如果该行还有数字，将下一个数字放入堆中
            pq.push({a[row][row + 1], row});
        }
    }
    cout << ans << endl;
    return 0;
}

时间复杂度: $O(n^2 \log n)$，其中 $n$ 为矩阵的大小。

空间复杂度: $O(n)$，主要是用来存储堆。