无
blablabla
样例
无
算法1
(暴力出奇迹) $O(n^4)$
求出前缀和,枚举矩阵坐上角的点和右下角的点,求出最优解
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int ma[110][110],sum[110][110];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
scanf("%d",&ma[i][j]);
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
sum[i][j]=ma[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
}
long long maxx=-0x7fffffff;
for(int x1=0;x1<=n;++x1){
for(int y1=0;y1<=n;++y1){
for(int x2=x1+1;x2<=n;++x2){
for(int y2=y1+1;y2<=n;++y2){
long long temp=sum[x2][y2]-sum[x2][y1]-sum[x1][y2]+sum[x1][y1];
maxx=max(maxx,temp);
}
}
}
}
cout<<maxx;
}
彩笔
别骂了别骂了,我知道我是煞笔了