按题意分成两次找。第一次时,若有多种可能,记录所有情况,然后分别找第二次最大值,最后比较。 在找最大值时,看成函数的形式,将四种情况加起来算。对于特殊的对角线情况则特判。 求指出代码错误或是指出思路问题。
#include<bits/stdc++.h>
using namespace std;
int Read();
int n;
int a[1007][1007],b[1007][1007];
int maxn[1007],tot,ans,thistime,maxn2;
int main(){
n=Read();
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
a[i][j]=Read();
for(int t=2;t<n;++t){
thistime=0;
for(int i=t;i<=n;++i)thistime+=a[i][i-t+1];
for(int i=t-1;i>=1;--i)thistime+=a[i][-i+t+1];
for(int i=2;i<=n-t+1;++i)thistime+=a[i][i+t-1];
for(int i=n-t+2;i<n;++i)thistime+=a[i][-i+2*n-t+1];
if(thistime==maxn[0]){
maxn[++tot]=t;
}
if(thistime>maxn[0]){
memset(maxn,0,sizeof(maxn));
maxn[0]=thistime;
tot=0;
maxn[++tot]=t;
}
}
thistime=0;
for(int i=1;i<=n;++i)thistime+=a[i][i];
if(thistime>maxn[0]){
memset(maxn,0,sizeof(maxn));
maxn[0]=thistime;
tot=0;
maxn[++tot]=1;
}
if(thistime==maxn[0]){
maxn[++tot]=1;
}
thistime=0;
for(int i=1;i<=n;++i)thistime+=a[i][n-i+1];
if(thistime>maxn[0]){
memset(maxn,0,sizeof(maxn));
maxn[0]=thistime;
tot=0;
maxn[++tot]=n;
}
if(thistime==maxn[0]){
maxn[++tot]=n;
}
for(int iii=1;iii<=tot;++iii){
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
b[i][j]=a[i][j];
int maxi1=maxn[iii];
if(maxi1!=1&&maxi1!=n)
for(int t=maxi1;t==maxi1;++t){
for(int i=t;i<=n;++i)b[i][i-t+1]=0;
for(int i=t-1;i>=1;--i)b[i][-i+t+1]=0;
for(int i=2;i<=n-t+1;++i)b[i][i+t-1]=0;
for(int i=n-t+2;i<n;++i)b[i][-i+2*n-t+1]=0;
}
if(maxi1==1)
for(int i=1;i<=n;++i)b[i][i]=0;
if(maxi1==n)
for(int i=1;i<=n;++i)b[i][-i+n+1]=0;
for(int t=2;t<n;++t){
thistime=0;
for(int i=t;i<=n;++i)thistime+=b[i][i-t+1];
for(int i=t-1;i>=1;--i)thistime+=b[i][-i+t+1];
for(int i=2;i<=n-t+1;++i)thistime+=b[i][i+t-1];
for(int i=n-t+2;i<n;++i)thistime+=b[i][-i+2*n-t+1];
if(thistime>maxn2){maxn2=thistime;}
}
thistime=0;
for(int i=1;i<=n;++i)thistime+=b[i][i];
if(thistime>maxn2){maxn2=thistime;}
thistime=0;
for(int i=1;i<=n;++i)thistime+=b[i][n-i+1];
if(thistime>maxn2){maxn2=thistime;}
}
// cout<<maxn[0]<<" "<<maxn2<<"\n";
cout<<maxn[0]+maxn2<<"\n";
return 0;
}
int Read(){
char ch=getchar();
int res=0,flag=1;
while(ch<'0'||ch>'9'){
if(ch=='-')flag=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
return flag*res;
}