用C++完成一下题目:给定一个M行N列的矩阵,要求你求得子矩阵(x1, y1), (x2, y2)的内所有元素的和。其中(x1, y1)和(x2, y2)是子矩阵的两个顶点。 输入 第一行输入包括三个数字M N Q。 接下来M行每行N个整数,表示需要处理的矩阵。 接下来Q行每行四个整数,表示子矩阵的方位。 输出 对于每一次询问,输出子矩阵内所有元素的和。
时间: 2023-06-06 17:05:12 浏览: 136
抱歉,我可以回答这个问题。以下是给定矩阵求子矩阵和的C代码,该代码使用动态规划的思路实现:
#include<stdio.h>
int main(){
int M, N, Q;
scanf("%d %d %d", &M, &N, &Q);
int matrix[M][N]; // 定义矩阵
for(int i = 0; i < M; i++){
for(int j = 0; j < N; j++){
scanf("%d", &matrix[i][j]);
}
}
int dp[M+1][N+1]; // 定义dp数组
for(int i = 0; i <= M; i++){
dp[i][0] = 0;
}
for(int j = 0; j <= N; j++){
dp[0][j] = 0;
}
for(int i = 1; i <= M; i++){
for(int j = 1; j <= N; j++){
dp[i][j] = matrix[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]; // dp转移方程
}
}
for(int i = 0; i < Q; i++){ // 处理每一个询问
int x1, y1, x2, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
printf("%d\n", dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]); // 输出子矩阵和
}
return 0;
}
阅读全文