简单二维前缀和求助

Stfb @ 2024-08-11 10:18:24

#include <cstdio>
#include <cstring>
#define N 125
using namespace std;
int n,a[N][N],sum[N][N],ans=0;
int max(int x,int y){if(x<y)return y;return x;}
int main()
{
    memset(sum,0,sizeof(sum));
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            scanf("%d",&a[i][j]),sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
    for(int x1=1;x1<=n;++x1)
        for(int y1=1;y1<=n;++y1)
            for(int x2=1;x2<=x1;++x2)
                for(int y2=1;y2<=y1;++y2)
                    ans=max(ans,sum[x1][y1]-sum[x1][y2]-sum[x2][y1]+sum[x2][y2]);
    printf("%d\n",ans);
    return 0;
}

by _lxc__ @ 2024-08-11 10:19:26

#include<bits/stdc++.h>
using namespace std;
int n,a[110][110],s[110][110];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
    }
    int maxx=-1000000;
    for(int a=1;a<=n;a++){
        for(int b=1;b<=n;b++){
            for(int c=a;c<=n;c++){
                for(int d=b;d<=n;d++){
                    int now=s[c][d]-s[a-1][d]-s[c][b-1]+s[a-1][b-1];
                    maxx=max(now,maxx);
                }
            }
        }
    }
    cout<<maxx;
    return 0;
}

by Stfb @ 2024-08-11 10:21:58

@_lxc___ 我先枚举大矩形怎么不行了

by _lxc__ @ 2024-08-11 10:45:14

@Stfb

你的枚举范围+权和范围不对

by _lxc__ @ 2024-08-11 10:45:45

@_lxc___

是权和公式

by tangyiqi @ 2024-08-17 15:59:00

@Stfb
涉及土地的事情我们可不能含糊

by tangyiqi @ 2024-08-17 17:07:08

@Stfb
我也是解出来了

#include<bits/stdc++.h>
#define u using namespace std;
#define ll long long
#define s scanf
#define p printf
#define f for
u
int a[120][120],n,ans,b[120][120];
int main() {
    s("%d",&n);
    f(int i = 1;i<=n;i++){
        f(int j = 1;j<=n;j++){
            s("%d",&a[i][j]);
            b[i][j] = b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
        }
    }
    ans = a[1][1];
    f(int x1 = 1;x1<=n;x1++){
        f(int x2 = x1;x2<=n;x2++){
            f(int y1 = 1;y1<=n;y1++){
                f(int y2 = y1;y2<=n;y2++){
                    ans = max(ans,b[x2][y2]-b[x1-1][y2]-b[x2][y1-1]+b[x1-1][y1-1]);
                }
            }
        }
    }
    p("%d",ans);
    return 0;
}

求关，谢谢