官方题解｜登塔

动态规划

对于本题，我们先从常规思路入手，考虑从第 $i$ 层向第 $i + 1$ 层的状态转移。设 $f[i][j]$ 表示处于第 $i$ 层的第 $j$ 个房间时所能取得的最大值。那么状态转移方程为 $f[i + 1][k] = \max(f[i][j]) + a[i + 1][k]$，其中 $j \in \{1, 2, \cdots, n\}$ 且 $j \neq k$。

从这个转移方程可以看出，$f[i + 1][j]$ 的转移核心在于找出第 $i$ 层除第 $j$ 个房间之外能取得的最大价值。假设第 $i$ 层价值最大的房间编号为 $j$，那么在第 $i + 1$ 层中，除了第 $j$ 号房间外，其他房间都可以从第 $i$ 层的 $j$ 号房间移动过来，从而获取最大价值。而第 $i + 1$ 层的 $j$ 号房间，则可以从第 $i$ 层价值次大的房间转移到达。

基于此，我们发现只需记录每一层价值最大的两个房间的编号，就能实现向下一层的状态转移。这种方法的时间复杂度为 $O(nm)$。

注意 m == 1的状况他会被困在第一层

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

int main() {
   ios::sync_with_stdio(0),cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<i64> > arr(n + 1, vector<i64>(m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    vector<priority_queue<pair<i64, int>, vector<pair<i64, int> >, greater<> > > f(n + 1);
    f[0].emplace(0, 0);
    for (int i = 1; i <= n; i++) {
        if (f[i - 1].empty()) continue;
        for (int j = 1; j <= m; j++) {
            auto t = f[i - 1].top();
            f[i - 1].pop();
            if (!f[i - 1].empty() && f[i - 1].top().second != j) {
                f[i].emplace(arr[i][j] + f[i - 1].top().first, j);
            } else {
                if (t.second != j)
                    f[i].emplace(arr[i][j] + t.first, j);
            }
            f[i - 1].emplace(t);
            while (f[i].size() > 2) f[i].pop();
        }
    }
    i64 maxs = 0;
    for (int i = 1; i <= n; i++) {
        while (!f[i].empty()) {
            maxs = max(maxs, f[i].top().first);
            f[i].pop();
        }
    }
    cout << maxs << endl;
}