题目描述
blablabla
样例
#include<iostream>
#include<vector>
using namespace std;
const int N = 1010;
int a[N][N], sum[N][N];
int main()
{
int x,y;
cin>>x>>y;
int l;
cin>>l;
for (int i=0;i<x;i++)
{
for (int j=0;j<y;j++)
{
cin>>a[i][j];
}
}
for (int j=0;j<y+1;j++)
{
sum[0][j]=0;
}
for (int i=0;i<y+1;i++)
{
sum[i][0]=0;
}
for (int i=1;i<x+1;i++)
{
for (int j=1;j<y+1;j++)
{
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i-1][j-1];
}
}
// for (int i=0;i<x+1;i++)
// {
// for(int j=0;j<y+1;j++)
// {
// cout<<sum[i][j]<<" ";
// }
// cout<<"\n";
// }
int x1,y1,x2,y2;
while(l)
{
l--;
cin>>x1>>y1>>x2>>y2;
int son=sum[x2][y2]+sum[x1-1][y1-1]-sum[x2][y1-1]-sum[x1-1][y2];
cout<<son<<endl;
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla