e911 - 108 p5. 收入分析

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個矩陣，代表某地區的收入分布。矩陣中的每個元素代表該位置的收入。題目要求計算多個查詢矩形區域的總收入。每個查詢給定矩形區域的左上角和右下角座標。

解題思路

本題的核心思想是使用前綴和 (Prefix Sum) 技術來高效地計算矩形區域的總和。首先，我們計算一個新的矩陣 dp，其中 dp[i][j] 儲存了原始矩陣中 (1, 1) 到 (i, j) 的所有元素的總和。計算 dp[i][j] 的公式為 dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + original_matrix[i][j]。

計算完前綴和矩陣後，對於每個查詢矩形，我們可以使用以下公式計算其總和：sum = dp[x2+1][y2+1] - dp[x2+1][y1] - dp[x1][y2+1] + dp[x1][y1]。其中 (x1, y1) 是左上角座標，(x2, y2) 是右下角座標。

複雜度分析

• 時間複雜度: O(mn + k)，其中 m 和 n 是矩陣的維度，k 是查詢的數量。計算前綴和矩陣需要 O(mn) 的時間，處理每個查詢需要 O(1) 的時間，因此總時間複雜度為 O(m*n + k)。
• 空間複雜度: O(m*n)，因為我們需要儲存前綴和矩陣 dp。

程式碼

#include <iostream>
using namespace std;
int dp[1005][1005],n,m,k,x1,y1,x2,y2;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> m >> n;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin >> dp[i][j];
			dp[i][j]+=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
			//cout << dp[i][j] << " ";
		}
		//cout << "\n";
	}
	cin >> k;
	for(int i=0;i<k;++i){
		cin >> y1 >> y2 >> x1 >> x2;
		if(x1>x2){
			swap(x1,x2);
		}
		if(y1>y2){
			swap(y1,y2);
		}
		cout << dp[x2+1][y2+1]-dp[x2+1][y1]-dp[x1][y2+1]+dp[x1][y1] << " "; 
	}
}