题解：P11293 [NOISG2022 Qualification] L-Board

题目链接

• 洛谷 P11293 [NOISG2022 Qualification] L-Board

解题思路

考虑维护四个数组 $u_{i,j},d_{i,j},l_{i,j},r_{i,j}$ 分别表示以位置 $(i,j)$ 为起点，在其上、下、左、右四个方向上，一定选择该点的最大区间和，显然可以 DP 维护。

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

参考代码

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

const int N = 1005;
int n , m;
long long a[N][N] , u[N][N] , d[N][N] , l[N][N] , r[N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
        {
            cin >> a[i][j];
            u[i][j] = max(u[i - 1][j] , 0ll) + a[i][j];
            l[i][j] = max(l[i][j - 1] , 0ll) + a[i][j];
        }
    for(int i = n ; i >= 1 ; i--)
        for(int j = m ; j >= 1 ; j--)
        {
            d[i][j] = max(d[i + 1][j] , 0ll) + a[i][j];
            r[i][j] = max(r[i][j + 1] , 0ll) + a[i][j];
        }
    long long ans = -0x3f3f3f3f;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
        {
            ans = max(ans , max(l[i][j] , r[i][j]) + max(u[i][j] , d[i][j]) - a[i][j]);
        }
    cout << ans << '\n';
    return 0;
}