0
已解决
初级天翼
题目描述 Description
现在有一个m行n列的非负矩阵，要求你找到x个子矩阵，输出每个子矩阵的所有元素的和。 对于每个子矩阵要求输入第a行第b列的元素是其左上角的元素，第c行第d列的元素是其右下角的元素。
输入描述 Input Description
第1行：m n
第2行到第m+1行：m*n的矩阵
第m+2行：x
最后x行：四个整数 a , b , c , d
输出描述 Output Description
共x行，第i行为第i个子矩阵的所有元素之和
样例输入 Sample Input
3 5 1 2 3 4 5 3 2 1 4 7 2 4 2 1 2 3 1 1 3 5 2 2 3 3 1 1 3 3
样例输出 Sample Output
43 9 20
数据范围及提示 Data Size & Hint
1<=m,n<=300
x<=300
1<=a<=c<=n
1<=b<=d<=m
0
已采纳
中级光能
要用到数组
0
资深天翼
这道题三重循环暴力可以解决，而我用的是动态规划（也可以说是前缀和）。
边读入边写动态转移方程：
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
cin>>a[i][j];
f[i][j]+=f[i-1][j]+f[i][j-1]+a[i][j]-f[i-1][j-1];
}
}
最后用循环读入4个数，
输出：
cout<<f[c][d]-f[a-1][d]-f[c][b-1]+f[a-1][b-1]<<endl;
陆麟瑞在2018-03-11 17:21:27追加了内容
有什么错的，再@我
0
缔造者之神
1
0
资深光能
二维树状数组
