当前位置：首页 > article >正文

子矩阵的和（矩阵前缀和）

article 2024/11/22 10:29:21

题目链接：用户登录 - C语言网

在这里可以模拟一下就知道了，
记录每个（0，0）到（i,j）的矩阵和
然后区间子矩阵的和，就减去多余的部分的矩阵和就可以得到了子矩阵的和

然后这里最好使用下标 1 ~ n 到 1 ~ m 存储，这样就可以方便，根据一条规律来使用即可。

初始化函数

// 初始化矩阵前缀和
inline void Init(){
    for(int i = 1;i <= n;++i)
	    for(int j = 1;j <= m;++j)
    	    s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1];
}

获取矩阵和函数

// 根据左上角坐标以及右下角坐标获取矩阵和
inline int getSum(PII p1,PII p2){
	int x1 = p1.x,y1=p1.y;
	int x2 = p2.x,y2=p2.y;
	return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}

题解代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
using PII = pair<int,int>;
const int N = 510;
int a[N][N],s[N][N],n,m,k,ans;
// 初始化矩阵前缀和
inline void Init(){
    for(int i = 1;i <= n;++i)
	    for(int j = 1;j <= m;++j)
    	    s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1];
}

// 根据左上角坐标以及右下角坐标获取矩阵和
inline int getSum(PII p1,PII p2){
	int x1 = p1.x,y1=p1.y;
	int x2 = p2.x,y2=p2.y;
	return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}
signed main(){
	IOS;
	cin >> n;
	m = n;
	for(int i = 1;i <= n;++i)
	    for(int j = 1;j <= m;++j)
			cin >> a[i][j];

// 初始化矩阵前缀和
	Init();
	
// 	循环遍历所有上下坐标，并获取矩阵和
	for(int i = 1;i <= n;++i){
		for(int j = 1;j <= m;++j){
			PII leftUp = PII(i,j);
			for(int x = i;x <= n;++x){
			    for(int y = j;y <= m;++y){
			    	PII rightDown = PII(x,y);
					int sum = getSum(leftUp,rightDown);
					ans = max(sum,ans);
				}
			}
		}
	}

	cout << ans << endl;
	return 0;
}