怎么做网站相册,帮助安装wordpress,wordpress中文主,昆明营销型网站建设公司【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com) 理解题意#xff1a; 要求的是(x1,y1) - (x2,y2)这段区间的和。
解法#xff1a;二维前缀和 1. 和一维前缀和一样#xff0c;需要有一个同等规模的dp数组#xff0c;用来保存一段连续区域的和。
在二维dp中#xff0…【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com) 理解题意 要求的是(x1,y1) - (x2,y2)这段区间的和。
解法二维前缀和 1. 和一维前缀和一样需要有一个同等规模的dp数组用来保存一段连续区域的和。
在二维dp中可以把数组分为四部分如下图
dp[xi][yi] 求的是由(1,1) - (xi,yi)区域的和就是算ABCD的和。而在此中直接求B,C的值可不好求因为在之前的dp数组中找不到这就与一维数组的dp不同了所以结合一下先求AB,AC的和再减去多加的A即可。
2.使用前缀和dp
要求的是中间一段区间的面积D
int main()
{//1.把值输入到原始数组int n 0,m 0,q 0;cin n m q;vectorvectorint arr(n1,vectorint(m1));for(int i 1;in;i)for(int j 1;jm;j)cin arr[i][j];//2.创建dp数组vectorvectorlong long int dp(n1,vectorlong long int(m1));for(int i 1;in;i)for(int j 1;jm;j)dp[i][j] dp[i-1][j] dp[i][j-1] arr[i][j] - dp[i-1][j-1];//3.使用dp数组int x1 0,y1 0,x2 0,y2 0;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;}
}
