1. 题目解析
题目链接:DP35 【模板】二维前缀和
这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。
核心在于计算题目所给二维区间数组元素和返回即可。
2. 算法原理
和上题了类似的方法,使用dp数组来保存[1,1]到[x,y]的和,这里不过多赘述,之间看代码更容易理解。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> arr(n + 1, vector<int>(m + 1));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> arr[i][j];
vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
int x1, x2, y1, y2;
while(q--)
{
cin >> x1 >> y1 >> x2 >> y2;
cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
}
return 0;
}
// 64 位输出请用 printf("%lld")
The Last
嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。
觉得有点收获的话,不妨给我点个赞吧!
如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~