题解 P7626 [COCI2011-2012#1] MATRIX

· · 题解

Solution P7626 [COCI2011-2012#1] MATRIX

思路：

首先，我们可以想到暴力求解。对每一个子矩阵的长宽、整个矩阵长宽进行循环，暴力求解。但是 N<=400 ，显然这种4~5层循环的不行。所以我们要想怎样优化。

首先，子矩阵长宽、整个矩阵长、宽这三层循环是不能去掉的。那我们就想怎样让求对角线长度的时间复杂度尽量低。

所以，我们可以用前缀和对两条对角线进行计数。每个点有两个对角线运算。

别的没有什么要注意的，详见代码。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[405][405],sum,x[405][405],y[405][405];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            x[i][j]=x[i-1][j-1]+a[i][j];//进行前缀和计数，x[][]表示主对角线
            y[i][j]=y[i-1][j+1]+a[i][j];//y[][]表示副对角线
        }
    }
    int A,B;
    for(int k=1;k<=n;k++){
        for(int i=k;i<=n;i++){
            for(int j=k;j<=n;j++){
                A=x[i][j]-x[i-k][j-k];//计算每个子矩阵的主对角线和副对角线长度
                B=y[i][j-k+1]-y[i-k][j+1];
                sum=max(sum,A-B);//进行运算
            }
        }
    }
    cout<<sum;
    return 0;
}

看了这么久，点个赞再走吧