爆0求助

P1719 最大加权矩形

Miracle_InDream @ 2023-10-22 14:17:55

#include<bits/stdc++.h>
using namespace std;
int n;
int a[125][125],sum[125][125],maxx=0;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    sum[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(sum[i][j]>maxx)
                maxx=sum[i][j];
        }
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=2;j<=n;j++)
        {
            for(int k=1;k<i;k++)
            {
                for(int l=1;l<j;l++)
                {
                    if(sum[i][j]-sum[i][l]-sum[j][k]+sum[k][l]>maxx)
                        maxx=sum[i][j]-sum[i][l]-sum[j][k]+sum[k][l];
                }
            }
        }
    }
    cout<<maxx;
    return 0;
}

by Ace_FutureDream @ 2023-10-29 14:20:09

@shooting__star

if(sum[i][j]-sum[i][l]-sum[j][k]+sum[k][l]>maxx) maxx=sum[i][j]-sum[i][l]-sum[j][k]+sum[k][l];

改成

if(sum[i][j]-sum[i][l-1]-sum[k-1][j]+sum[k-1][l-1]>maxx) maxx=sum[i][j]-sum[i][l-1]-sum[k-1][j]+sum[k-1][l-1]; maxx初始值改成-1e9

自行理解


|