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

题目链接：用户登录 - 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;
}

最后提交