自动搬运

查看原文

来自洛谷，原作者为

	Aiopr_2378 沿湍流兮望归舟

搬运于2025-08-24 22:31:40，当前版本为作者最后更新于2021-07-13 10:39:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}

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