HDU 1559 最大子矩陣：二維前綴和 O(n²m²) → O(n²m) 優化

HDU 1559：固定大小子矩陣最大和（二維前綴和）

給定 n×m 矩陣，找 x×y 子矩陣最大和。構建二維前綴和 `sum[i][j]` 表示 (1,1) 到 (i,j) 矩形和。任意子矩陣 (x1,y1)-(x2,y2) 和 = `sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]`。枚舉左上角 O(nm) 直接算出。

完整代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[1001][1001];
int main(){
    int T; scanf("%d",&T);
    while(T--){
        int n,m,x,y; scanf("%d%d%d%d",&n,&m,&x,&y);
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                LL v; scanf("%lld",&v);
                a[i][j]=a[i][j-1]+v; // 行前綴和
            }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                a[i][j]+=a[i-1][j]; // 列累加得二維前綴和
        LL ans=LLONG_MIN;
        for(int i=1;i<=n-x+1;i++)
            for(int j=1;j<=m-y+1;j++){
                LL cur=a[i+x-1][j+y-1]-a[i-1][j+y-1]-a[i+x-1][j-1]+a[i-1][j-1];
                ans=max(ans,cur);
            }
        printf("%lld\n",ans);
    }
    return 0;
}

優化要點

• 分兩步構建前綴和：先行後列，緩存友好。
• 枚舉左上角而非右下角，邊界更直觀。
• 用 `LLONG_MIN` 初始化應對全負數矩陣。