题解

明显的 DP。

设 $dp_{i,j}$ 表示到达 $i$ 层，目前位于房间 $j$ 的最大收获。

状态转移实在太显然了：

$$dp_{i,j}=\max(\max_{1 \leq k < j}{dp_{i-1,k}},\max_{j < k \leq m}{dp_{i-1,k}})+a_{i,j}$$

发现可以边跑边记录上一层的最大值，这样转移复杂度就降为 $O(1)$ 了。

但是如果上一层的最大值的位置刚好等于 $j$ 的话，$j$ 房间开不了门。所以我们还要维护一个次大值。

这就很简单了。

时间复杂度：$O(nm)$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
const ll MAXN=2e5+25;
ll n,m,fir,sec,newfir,newsec,ans;
vector<ll> a[MAXN],dp[MAXN];
int main(){
    cin>>n>>m;
    for(ll i=0;i<=n+1;i++){
        a[i].resize(m+2);
        dp[i].resize(m+2);
    }
    for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) cin>>a[i][j];
    for(ll i=1;i<=n;i++){
        newfir=newsec=0;
        for(ll j=1;j<=m;j++){
            if(fir^j) dp[i][j]=dp[i-1][fir]+a[i][j];
            else if(sec) dp[i][j]=dp[i-1][sec]+a[i][j];
            if(dp[i][j]>=dp[i][newfir]){
                newsec=newfir;
                newfir=j;
            }
            else if(dp[i][j]>dp[i][newsec]) newsec=j;
            ans=max(dp[i][j],ans);
        }
        fir=newfir;
        sec=newsec;
    }
    cout<<ans;
    return 0;
}