d735 - Minimum Sum
題目描述
題目要求找出一個 N x N 陣列中，和最小的子矩陣的值。子矩陣必須有正面積。
解題思路
程式碼使用前綴和與暴力法來解決問題。首先，計算每個 row 的前綴和，以便快速計算任意列區間的和。然後，使用兩層迴圈遍歷所有可能的左上角和右下角，定義一個矩形區域。對於每個矩形區域，計算其總和，並更新最小和。如果陣列中的所有元素都是非負數，則最小和就是陣列中的最小值。
複雜度分析
- 時間複雜度: O(n^4)
- 空間複雜度: O(n^2)
程式碼
#include <iostream>
using namespace std;
int a[102][102],n;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
int ans=0,a2=1000000;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
cin >> a[i][j];
a2=min(a[i][j],a2);
a[i][j]+=a[i][j-1];
}
}
for(int i=1;i<=n;++i){
for(int j=i;j<=n;++j){
int buf=0;
for(int k=1;k<=n;++k){
if(buf+(a[k][j]-a[k][i-1])>0)
buf=0;
else
buf+=a[k][j]-a[k][i-1];
ans=min(buf,ans);
}
}
}
if(a2>=0)
cout << a2 << "\n";
else
cout << ans << "\n";
}
}