b840 - 104北二4.農作物採收問題
題目描述
題目要求找出一個 N x N 的矩陣中，連續區域（矩形）的最大總和。矩陣中的每個元素代表該單元採收的得分，可以是正數（收益）或負數（虧損）。
解題思路
本題使用動態規劃和前綴和的思想來解決。首先，計算一個前綴和矩陣 dp[i][j]，其中 dp[i][j] 表示矩陣中 (1, 1) 到 (i, j) 的所有元素的總和。然後，遍歷所有可能的矩形區域，利用前綴和矩陣快速計算每個矩形區域的總和，並更新最大總和。
具體來說，對於一個矩形區域 (i, j) 到 (ii, jj)，其總和可以通過以下公式計算：
dp[ii][jj] - dp[i-1][jj] - dp[ii][j-1] + dp[i-1][j-1]
通過遍歷所有可能的矩形區域，找到最大總和。
複雜度分析
- 時間複雜度: O(n^4) (四個迴圈遍歷所有可能的矩形)
- 空間複雜度: O(n^2) (用於儲存前綴和矩陣
dp)
程式碼
#include <iostream>
using namespace std;
int a[25][25],n,ans,dp[25][25];
int main(){
cin >> n;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
cin >> a[i][j];
dp[i][j]=a[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
}
}
for(int i=0;i<=n;++i){
for(int j=0;j<=n;++j){
for(int ii=i;ii<=n;++ii){
for(int jj=j;jj<=n;++jj){
ans=max(ans,dp[ii][jj]-dp[i][jj]-dp[ii][j]+dp[i][j]);
}
}
}
}
cout << ans;
}