题解 UVA108 【Maximum Sum】
Mars_Dingdang
2021-01-14 17:02:21
由于本题的数据规模极小,用简单的二维前缀和维护,暴力枚举即可。
## 题目大意
有一个 $n\times n$ 的矩阵,元素 $a_{i_j}\in [-127,127]\cap \mathbb Z$,求该元素的最大子矩阵。
一个子矩阵是任意在总矩阵中大小为 $1
\times 1$ 或更大的邻近子数组。
## 大体思路
正如我在第一行所说,由于本题的数据规模极小,用简单的二维前缀和维护,暴力枚举即可。
好了,思路没了。
那么,本题的关键就是二维前缀和的思想。普通的前缀和是记录某一“线段”上所有数的和,即 $S_k=\sum\limits_{i=1}^k a_i$。因此,区间 $[l,r]$ 的元素和可以由容斥得到:$sum[l,r]=S_{r}-S_{l-1}$。
而推广到二维平面也是一样。如下图所示,用 $S_{i,j}$ 表示矩阵起点(或坐标原点)到点 $(i,j)$(包含)的矩阵内部的元素之和,及下图染色区域的元素之和。由容斥可得:
$$S_{m,n}=\sum_{i=1}^m\sum_{j=1}^na_{i,j}=a_{m,n}+S_{m-1,n}+S_{m,n-1}-S_{m-1,n-1}$$
![](https://cdn.luogu.com.cn/upload/image_hosting/itdrwwxp.png)
在计算 $S_{i,j}$ 的过程中,由几部分组成:本身所代表的元素(绿色),横坐标减一的矩阵和(红色),纵坐标减一的矩阵和(黄色),以及重叠部分(红+黄=橙色)。其中,重叠部分被计算两次,因此减去,即
$$[m,n]=[m-1,n]\cup [m,n-1]+ a_{m,n}=[m-1,n]+ [m,n-1]+ a_{m,n}-[m-1,n]\cap[m,n-1]$$
然后模拟即可,复杂度近似 $O(n^4)$。
## 完整代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(ii,aa,bb) for(re int ii=aa;ii<=bb;ii++)
#define Rep(ii,aa,bb) for(re int ii=aa;ii>=bb;ii--)
typedef long long ll;
typedef unsigned long long ull;
const int maxn=105;
const int inf=-2e9+7;
namespace IO_ReadWrite{
#define re register
#define gg getchar()
template <typename T>
inline void read(T &x){
x=0;re T f=1;re char c=gg;
while(c>57||c<48){if(c=='-') f=-1;c=gg;}
while(c>=48&&c<=57){x=(x<<1)+(x<<3)+(c^48);c=gg;}
x*=f;return;
}
inline void ReadChar(char &c){
c=gg;
while(!isalpha(c)) c=gg;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar('0'+x%10);
}
template <typename T>
inline void writeln(T x){write(x);putchar('\n');}
}
using namespace IO_ReadWrite;//快读
int n,a[maxn][maxn],sum[maxn][maxn],ans=-1;
//a是原矩阵,sum是二维前缀和
int main(){
read(n);
rep(i,1,n){
rep(j,1,n){
read(a[i][j]);//输入
sum[i][j]=(a[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]);
//利用容斥计算前缀和
ans=max(ans,a[i][j]);
}
}
rep(i,1,n-1) {
rep(j,i,n-1){
for(re int line=i+1;line<=n;line++) {
for(re int row=j+1;row<=n;row++){//暴力枚举
int s=sum[line][row]-sum[i-1][row]-sum[line][j-1]+sum[i-1][j-1];//当前矩阵(思路同上)
ans=max(ans,s);//取最大子矩阵
}
}
}
}
writeln(ans);//输出+换行
return 0;
}
```