f162 - 4. 獵人與斯芬克斯
題目描述
題目給定一個 n x m 的矩陣，矩陣中的每個元素都是一個正整數。獵人需要從矩陣的左上角 (0, 0) 出發，走到矩陣的右下角 (n-1, m-1)。獵人每次只能向右或向下移動。斯芬克斯會給獵人一個上限 k，獵人走過的路上，任何子矩陣的和都不能超過 k。題目要求找到獵人走過的最大路徑和，同時滿足斯芬克斯的限制。
解題思路
本題的核心是計算所有可能的子矩陣的和，並檢查是否超過上限 k。為了提高效率，我們使用動態規劃 (Dynamic Programming) 來預先計算出每個位置 (i, j) 的前綴和。dp[i][j] 表示從 (0, 0) 到 (i, j) 的矩陣元素的總和。
接著，對於每個位置 (i, j)，我們遍歷所有可能的子矩陣，其左上角為 (0, 0)，右下角為 (i, j)。利用前綴和的性質，我們可以快速計算出任何子矩陣的和。具體來說，子矩陣 (x1, y1) 到 (x2, y2) 的和可以表示為 dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]。
在計算每個子矩陣的和後，我們檢查它是否小於或等於 k。如果滿足條件，我們將其與當前的最大路徑和 ans 進行比較，並更新 ans。
複雜度分析
- 時間複雜度: O(n^2 * m^2)。因為需要遍歷所有可能的子矩陣，而子矩陣的數量是 O(n^2 * m^2)。
- 空間複雜度: O(n * m)。因為需要使用一個 n x m 的
dp陣列來存儲前綴和。
程式碼
#include <iostream>
using namespace std;
long long int k,n,m,ans;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> k >> n >> m;
long long int dp[n][m],a[n][m];
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
cin >> a[i][j];
if(i==0&&j==0){
dp[i][j]=a[i][j];
}
else if(i==0){
dp[i][j]=dp[i][j-1]+a[i][j];
}
else if(j==0){
dp[i][j]=dp[i-1][j]+a[i][j];
}
else{
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+a[i][j];
}
long long int tmp=dp[i][j],v;
for(int ii=0;ii<=i;++ii){
for(int jj=0;jj<=j;++jj){
if(ii==0&&jj==0){
v=tmp;
}
else if(ii==0){
v=tmp-dp[i][jj-1];
}
else if(jj==0){
v=tmp-dp[ii-1][j];
}
else{
v=tmp-dp[i][jj-1]-dp[ii-1][j]+dp[ii-1][jj-1];
}
if(v<=k)ans=max(ans,v);
}
}
}
}
cout << ans << "\n";
}