TZOJ 4475：The Coolest Sub

Coolest Sub"/>

TZOJ 4475：The Coolest Sub

【问题描述】
Given an N*N matrix, find the coolest square sub-matrix.
We define the cool value of the square matrix as X-Y where X indicating the sum of all integers of the main diagonal and Y indicating the sum of the other diagonal.

【输入格式】
The first line has a positive integer N (2 ≤ N ≤ 400), the size of the matrix.
The following N lines each contain N integers in the range [-1000, 1000], the elements of the matrix.

【输出格式】
Output the coolest value of a square sub-matrix.

【输入输出样例】
输入：
2
1 -2
4 5

输出：
4

【算法分析】
本题乍一看，以为是二维前缀和问题。事实上，它是两条对角线上的一维前缀和问题。
下图中的两条箭头，给出了两条对角线方向上的一维前缀和计算顺序。易得：
s1[i][j]=s1[i-1][j-1]+x;       //蓝色箭头方向↘
s2[i][j]=s2[i-1][j+1]+x;      //红色箭头方向↙
之后，根据一维前缀和的计算规则 及下图各点坐标，可得两条对角线上的差值为：s1[i+k][j+k]-s1[i-1][j-1]-(s2[i+k][j]-s2[i-1][j+k+1])，注意从点(i,j)开始计算。

【算法代码】 

#include<bits/stdc++.h>
using namespace std;const int maxn=405;
int s1[maxn][maxn]; //s1正对角线前缀和
int s2[maxn][maxn]; //s2反对角线前缀和int main() {int x;int ans=-0x3f3f3f3f;int n;cin>>n;for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {scanf("%d",&x);s1[i][j]=s1[i-1][j-1]+x; //方向↘s2[i][j]=s2[i-1][j+1]+x; //方向↙}}for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)for(int k=1; k<=min(n+1-i,n+1-j); k++) //小矩阵边长kans=max(ans,s1[i+k][j+k]-s1[i-1][j-1]-(s2[i+k][j]-s2[i-1][j+k+1]));cout<<ans<<endl;return 0;
}/*
in:
2
1 -2
4 5out:
4
*/

【参考文献】
.html