0ms 1.53MB

#include <stdio.h>
#include <stdlib.h>

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    
    int a[51][51] = {0};
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    
    // 使用滚动数组优化，只保存当前步和上一步的状态
    int dp[2][51][51] = {0};
    int cur = 0;
    
    for (int k = 2; k <= m + n; k++) {
        cur ^= 1; // 切换当前层
        for (int i = 1; i <= m && i <= k; i++) {
            for (int j = 1; j <= m && j <= k; j++) {
                int y1 = k - i;
                int y2 = k - j;
                
                if (y1 < 1 || y1 > n || y2 < 1 || y2 > n) {
                    dp[cur][i][j] = 0;
                    continue;
                }
                
                int val = a[i][y1];
                if (i != j || y1 != y2) {
                    val += a[j][y2];
                }
                
                int max_val = 0;
                max_val = max(max_val, dp[cur^1][i][j]);
                if (i > 1) max_val = max(max_val, dp[cur^1][i-1][j]);
                if (j > 1) max_val = max(max_val, dp[cur^1][i][j-1]);
                if (i > 1 && j > 1) max_val = max(max_val, dp[cur^1][i-1][j-1]);
                
                dp[cur][i][j] = max_val + val;
            }
        }
    }
    
    printf("%d\n", dp[cur][m][m]);
    
    return 0;
}