题解 UVA108 【Maximum Sum】

Mars_Dingdang

2021-01-14 17:02:21

Solution

由于本题的数据规模极小,用简单的二维前缀和维护,暴力枚举即可。 ## 题目大意 有一个 $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; } ```