暴力解40分

heboyue303 @ 2024-12-21 21:18:17

#include<bits/stdc++.h>
using namespace std;
int n,a[200][200],maxx;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int x=1;x<=n;x++){
        for(int y=1;y<=n;y++){
            for(int p=1;p<=n;p++){
                for(int q=1;q<=n;q++){
                    int s=0;
                    for(int z=x;z<=p;z++){
                        for(int k=y;k<=q;k++){
                            s+=a[z][k];
                        }
                    }
                    maxx=max(maxx,s);
                }
            }
        }
    }cout<<maxx;
    return 0;
}

by little_q_exist @ 2024-12-22 08:48:27

你的时间复杂度已经 O(n^6) 了，肯定是过不了的，学一下前缀和的知识可以优化成 O(n^4)

by Kicrosoft @ 2024-12-22 15:43:56

#include<bits/stdc++.h>
using namespace std;
int a[200][200],s[200][200];
int main(){
    int n,ans=-1e9;
    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];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int x=i;x<=n;x++){
                for(int y=j;y<=n;y++){
                    int sum=s[x][y]-s[x][j-1]-s[i-1][y]+s[i-1][j-1];
                    ans=max(sum,ans);
                }
            }
        }
    }
    cout << ans;
    return 0;
}