1 条题解

  • 0
    @ 2026-07-20 18:28:21
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    void solve(){
        ios::sync_with_stdio(0);
        cin.tie(NULL);
        cout.tie(NULL);
    
        int n,m;
        cin >> n >> m;
        
        vector<vector<int>>s;
        s.resize(n + 1,vector<int>(m + 1));
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                cin >> s[i][j];
            }
        }
        
        vector<vector<vector<int>>>dp;
        dp.resize(n + 1,vector<vector<int>>(m + 1,vector<int>(3 + 1,-1e18)));
        dp[1][1][1] = dp[1][1][2] = dp[1][1][3] = s[1][1];
        for(int j = 1;j <= m;j++){
            for(int i = 1;i <= n;i++){
                dp[i][j][1] = max({dp[i][j - 1][1],dp[i][j - 1][2],dp[i][j - 1][3]}) + s[i][j];
            }
            for(int i = 2;i <= n;i++){
                dp[i][j][2] = max(dp[i - 1][j][1],dp[i - 1][j][2]) + s[i][j];
            }
            for(int i = n - 1;i >= 1;i--){
                dp[i][j][3] = max(dp[i + 1][j][3],dp[i + 1][j][1]) + s[i][j];
            }
        }
        cout << max({dp[n][m][1],dp[n][m][2],dp[n][m][3]}) << "\n";
        return;
    }
    signed main(){
        int T = 1;
        while(T--){
            solve();
        }
        return 0;
    }
    
  • 1

信息

ID
1018
难度
9
分类
(无)
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者