本文共 2131 字，大约阅读时间需要 7 分钟。

题目

解

挺恶心的题。

代码

注释也懒得打了…

#include
   
    #include
    
     #include
     
      using namespace std;int n, a[1011][1011], f1[1011][1011], f2[1011][1011], ans;int q(int i){   	return f2[1][i] + f2[n-i+1][n]+ f1[n][n-i+1] + f1[n-i+1][n] - a[1][i] - a[i][1] - a[n-i+1][n] - a[n][n-i+1];}int cl(int i, int j){   	int l = (i+j)/2;	int anss = q(i) + q(j) - a[l][l-i+1] - a[n-l+i][n+1-l]	- a[l-i+1][l] - a[n+1-l][n-l+i];	return anss;                                                                                                                                                                                                                                                                                            } void work1(){   	ans = f1[n][n] + f2[1][n] - a[n/2+1][n/2+1];  //两条对角线 	for(int i = 2; i < n; ++i){     //左上到右下 + 其他 		if(i % 2 == 0) ans = max(ans, f1[n][n] + q(i));		else ans = max(ans, f1[n][n] + q(i) - a[(i+1)>>1][(i+1)>>1] - a[n-(i>>1)][n-(i>>1)]);	}	for(int i = 2; i < n; ++i){     //左下到右上 + 其他 		if(i % 2 == 0) ans = max(ans, f2[1][n] + q(i));		else ans = max(ans, f2[1][n] + q(i) - a[n-(i+n)/2+1][(i+n)>>1] - a[(i+n)>>1][n-(i+n)/2+1]);	}				}void work2(){   	ans = f1[n][n] + f2[1][n];  //两条对角线 	for(int i = 2; i < n; ++i){     //左上到右下 + 其他 		if(i % 2 == 0) ans = max(ans, f1[n][n] + q(i));		else ans = max(ans, f1[n][n] + q(i) - a[(i+1)>>1][(i+1)>>1] - a[n-(i>>1)][n-(i>>1)]);	}	for(int i = 2; i < n; ++i){     //左下到右上 + 其他 		if(i % 2 == 1) ans = max(ans, f2[1][n] + q(i));		else ans = max(ans, f2[1][n] + q(i) - a[n-(n+i)/2+1][(n+i)>>1] - a[(n+i)>>1][n-(n+i)/2+1]);	}	}int main(){   	scanf("%d", &n);	for(int i = 1; i <= n; ++i)		for(int j = 1; j <= n; ++j){   			scanf("%d", &a[i][j]);			f1[i][j] = f1[i-1][j-1] + a[i][j];		}	for(int i = n; i >= 1; --i)		for(int j = 1; j <= n; ++j)			f2[i][j] = f2[i+1][j-1] + a[i][j];	if(n % 2 == 1) work1();	else work2();	for(int i = 2; i < n; ++i)		for(int j = i; j < n; ++j){   			if(i!=j){     //其他相互 				if(i % 2 != j % 2) ans = max(ans, q(j) + q(i));				else ans = max(ans, cl(i,j));			}			ans = max(q(i), ans);		}	printf("%d", ans);}
     
    
   

转载地址：http://ewug.baihongyu.com/