a026 - APIO2009 1.采油区域
題目描述
題目要求在一個 M x N 的矩陣中找到三個互不相交的 K x K 的正方形區域，使得這些區域內的石油儲量總和最大。
解題思路
本題的核心思想是利用動態規劃和前綴和來高效地計算每個 K x K 區域的石油儲量，然後通過枚舉和貪心策略來尋找最佳的三個區域組合。
-
前綴和計算: 首先，使用前綴和技術計算出矩陣中任意子矩陣的石油儲量總和。這使得計算 K x K 區域的儲量變得非常快速，時間複雜度為 O(1)。
-
動態規劃 (DP): 使用多個 DP 陣列來儲存不同方向上的最大儲量。例如，
dplu[i][j]儲存從 (0, 0) 到 (i, j) 的區域內的最大儲量，dpru[i][j]儲存從 (i, j) 到 (n-1, m-1) 的區域內的最大儲量，以此類推。 -
枚舉和貪心: 程式碼中使用了多層迴圈來枚舉可能的區域組合。外層迴圈枚舉第一個區域的左上角，內層迴圈枚舉第二個和第三個區域。在枚舉過程中，利用 DP 陣列快速計算每個區域的儲量，並更新最大儲量。
-
Divide and Conquer: 程式碼中也體現了分治的思想，通過將問題分解為更小的子問題來解決。例如，通過計算
dplr[i]和dpud[j]來儲存特定行或列的最大儲量，然後在後續的計算中使用這些儲量。
複雜度分析
- 時間複雜度: O(n^2 * m^2)。主要體現在多層迴圈的枚舉和計算上。雖然使用了前綴和和 DP 來優化子矩陣的儲量計算，但整體的時間複雜度仍然受到枚舉的影響。
- 空間複雜度: O(n^2)。主要體現在儲存 DP 陣列所需的空間。
程式碼
#include <bits/stdc++.h>
#define ll int
using namespace std;
ll dp[1501][1501],d[1501][1501],n,m,k,ans,dplu[1501][1501],dpru[1501][1501],dpld[1501][1501],dprd[1501][1501],dplr[1501],dpud[1501];
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n >> m >> k;
for(ll i=1;i<=n;++i)
for(ll j=1;j<=m;++j){
cin >> dp[i][j];
dp[i][j]+=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1];
}
for(ll i=0;i<=n-k;++i)
for(ll j=0;j<=m-k;++j){
d[i][j]=dp[i+k][j+k]-dp[i+k][j]-dp[i][j+k]+dp[i][j];
dplr[i]=max(dplr[i],d[i][j]);
dpud[j]=max(dpud[j],d[i][j]);
}
for(ll i=0;i<=n-k;++i){
for(ll j=0;j<=m-k;++j)
dplu[i][j]=max({i?dplu[i-1][j]:0,j?dplu[i][j-1]:0,d[i][j]});
for(ll j=m-k;j>=0;--j)
dpru[i][j]=max({i?dpru[i-1][j]:0,dpru[i][j+1],d[i][j]});
}
for(ll i=n-k;i>=0;--i){
for(ll j=0;j<=m-k;++j)
dpld[i][j]=max({dpld[i+1][j],j?dpld[i][j-1]:0,d[i][j]});
for(ll j=m-k;j>=0;--j)
dprd[i][j]=max({dprd[i+1][j],dprd[i][j+1],d[i][j]});
}
for(ll i=0;i<=n-k;++i){
for(ll j=i+k,t=0;j<=n-k;++j){
t=max(t,dplr[j]);
ans=max(ans,dplu[i][m-k]+t+dpld[j+k][m-k]);
}
for(ll j=0;j<=m-k;++j){
ans=max(ans,dplu[i][m-k]+dpld[i+k][j]+dprd[i+k][j+k]);
ans=max(ans,dpld[i+k][m-k]+dplu[i][j]+dpru[i][j+k]);
}
}
for(ll i=0;i<=m-k;++i){
for(ll j=i+k,t=0;j<=m-k;++j){
t=max(t,dpud[j]);
ans=max(ans,dplu[n-k][i]+t+dpru[n-k][j+k]);
}
for(ll j=0;j<=n-k;++j){
ans=max(ans,dplu[n-k][i]+dpru[j][i+k]+dprd[j+k][i+k]);
ans=max(ans,dpru[n-k][i+k]+dplu[j][i]+dpld[j+k][i]);
}
}
cout << ans;
}