题解：P11293 [NOISG2022 Qualification] L-Board

zhhgdm · 2024-11-24 20:27:28 · 题解

题目大意

从一个棋盘选取一个 L 形、Γ 形、Ⴈ 形或 ⅃ 形的区域，使得区域的中数字的和最大。

注意，这个区域的不能是下图这样的：

因为他的“粗”是 2。

题目分析

既然“粗”只能是 1，那就相当于找到一个交点，从它的上或下选择一条直线（可以不选），再从左或右也选一条直线，使得拼接后数字值和最大，那肯定是选最长的两条直线喽。那么，我们就可以用最大子段和的方式向四个方向求以其为开头（结尾）的直线的最大和。

例（向上）：

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        pre[i][j]=max(0,pre[i][j-1])+a[i][j];
        // 如果发现前面 <0 了，就丢弃（这条直线只要我一个），否则求让我和前面连上
    }
}

完整代码

#include<bits/stdc++.h>
#define int long long // 十年 OI 一场空，不开 long long 见祖宗。
using namespace std;
int a[1005][1005];
int pre[1005][1005][4];
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }

    // 向上

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            pre[i][j][0]=max(0ll,pre[i][j-1][0])+a[i][j]; // max 不支持两个参数类型不同，写成 0 喜提 CE。
        }
    }

    // 向下

    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){
            pre[i][j][1]=max(0ll,pre[i][j+1][1])+a[i][j];
        }
    }

    // 向左

    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++){
            pre[i][j][2]=max(0ll,pre[i-1][j][2])+a[i][j];
        }
    }

    // 向右

    for(int j=m;j>=1;j--){
        for(int i=n;i>=1;i--){
            pre[i][j][3]=max(0ll,pre[i+1][j][3])+a[i][j];
        }
    }

    int maxn=LLONG_MIN; // 别忘了刚才 #define int long long 了
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            maxn=max({
                maxn,
                pre[i][j][0]+pre[i][j][2]-a[i][j], // ⅃ 形
                pre[i][j][1]+pre[i][j][2]-a[i][j], // Γ 形
                pre[i][j][0]+pre[i][j][3]-a[i][j], // ⅃ 形
                pre[i][j][1]+pre[i][j][3]-a[i][j] // Ⴈ 形
            });
        }
    }
    cout<<maxn;
}