题解：P11293 [NOISG 2022 Qualification] L-Board

HPXXZYY · 2025-03-02 21:38:31 · 题解

很显然，对于单个点来说，它的第一项对答案的贡献就是往左最大连续子段和和往右最大连续子段和的较大值，第二项对答案的贡献就是往上的最大连续子段和和往下的最大连续子段和的较大值，第三项是本身。

于是把问题转化为求最大连续子段和。

当然这个问题可以用一个经典的 dp 解决。但是对于一个退役的大学生来说，问题应该怎么复杂化怎么来。

连续和的问题一般都可以转化为前缀和。以往左的最大连续子段和为例，设 l_{i,j} 表示 (i,j) 往左的前缀和，即：

那么从 (i,j) 往左的最大连续子段和就是 l_{i,j} 减去最小的 l_{i,k}(0 \leq k <j)，其中 l_{i,0} 定义为 0。

注意代码实现的细节，挺多细节需要考虑的。

int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=read();

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            Left[i][j]=Left[i][j-1]+a[i][j];
        for(int j=m;j>=1;j--)
            Right[i][j]=Right[i][j+1]+a[i][j];

        minn[0]=0;
        for(int j=1;j<=m;j++)
            minn[j]=min(minn[j-1],Left[i][j-1]);
        for(int j=1;j<=m;j++)
            Left[i][j]-=minn[j];

        minn[m+1]=0;
        for(int j=m;j>=1;j--)
            minn[j]=min(minn[j+1],Right[i][j+1]);
        for(int j=m;j>=1;j--)
            Right[i][j]-=minn[j];
    }
    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++)
            Up[i][j]=Up[i-1][j]+a[i][j];
        for(int i=n;i>=1;i--)
            Down[i][j]=Down[i+1][j]+a[i][j];

        minn[0]=0;
        for(int i=1;i<=n;i++)
            minn[i]=min(minn[i-1],Up[i-1][j]);
        for(int i=1;i<=n;i++)
            Up[i][j]-=minn[i];

        minn[n+1]=0;
        for(int i=n;i>=1;i--)
            minn[i]=min(minn[i+1],Down[i+1][j]);
        for(int i=n;i>=1;i--)
            Down[i][j]-=minn[i];
    }

    ans=-1e18;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ckmax(ans,max(Up[i][j],Down[i][j])+max(Left[i][j],Right[i][j])-a[i][j]);

    printf("%lld",ans);

    return 0;
}