题目传送门
思路:
首先思考暴力,\(O(n^4)\) 的时间复杂度,不行。
那么我们这里就要运用到一点前缀和的知识了。
我们可以用前缀和对两条对角线进行计数。
每个点有两个对角线运算。
差不多是 \(O(n^2)\) 到 \(O(n^3)\)的时间复杂度。
而 \(n\leq400\) 稳过。
Code:
#include<bits/stdc++.h>
using namespace std;
long long n,m,ans,a[5][405][405];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[1][i][j];
a[2][i][j]=a[1][i][j];
a[1][i][j]=a[1][i][j]+a[1][i-1][j-1];
a[2][i][j]=a[2][i][j]+a[2][i-1][j+1];//前缀和
}
}
for(int k=1;k<=n;k++)
{
for(int i=k;i<=n;i++)
{
for(int j=k;j<=n;j++)
{
ans=max(ans,(a[1][i][j]-a[1][i-k][j-k])-(a[2][i][j-k+1]-a[2][i-k][j+1]));//求差的最大值
}
}
}
cout<<ans;
return 0;
}
标签:P7626,MATRIX,int,题解,复杂度,long,前缀
From: https://www.cnblogs.com/BadBadBad/p/P7626.html