BZOJ 1218 [HNOI2003] 激光炸彈：二維前綴和暴力枚舉優化

問題描述

地圖上有 N ≤ 10000 個目標，座標 (Xi, Yi) ∈ [0, 5000]，每個目標有價值。激光炸彈摧毀邊長為 R、邊平行座標軸的正方形內目標（邊界不算）。求一顆炸彈最大可摧毀價值總和（結果 ≤ 32767）。

解題關鍵：二維前綴和 + 窗口枚舉

由於座標範圍固定（5000×5000），可建立二維陣列 s[x][y] 記錄該座標目標價值和。利用二維前綴和 O(1) 查詢任意矩形區域和，再枚舉正方形左上角（或右下角）位置，取最大值。

前綴和構建

s[i][j] += s[i][j-1];  // 行前綴和
s[i][j] += s[i-1][j];  // 列前綴和

區域和查詢

正方形右下角 (i, j)，邊長 R，左上角 (i-R, j-R)：

sum = s[i][j] - s[i-R][j] - s[i][j-R] + s[i-R][j-R];

完整程式碼

#include 
using namespace std;
const int MAXN = 5005;
int s[MAXN][MAXN];

inline int read() {
    int x=0, f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

int main() {
    int n = read(), r = read();
    for (int i=1; i<=n; ++i) {
        int x = read()+1, y = read()+1, z = read();
        s[x][y] += z;  // 座標偏移 1，避免邊界判斷
    }
    // 二維前綴和
    for (int i=1; i<=5001; ++i)
        for (int j=1; j<=5001; ++j)
            s[i][j] += s[i][j-1];
    for (int i=1; i<=5001; ++i)
        for (int j=1; j<=5001; ++j)
            s[i][j] += s[i-1][j];
    // 枚舉右下角
    int ans = 0;
    for (int i=r; i<=5001; ++i)
        for (int j=r; j<=5001; ++j) {
            int tmp = s[i][j] - s[i-r][j] - s[i][j-r] + s[i-r][j-r];
            ans = max(ans, tmp);
        }
    printf("%d\n", ans);
    return 0;
}

複雜度分析

• 時間：O(MAX²) ≈ 2.5×10⁷ 操作，極快。
• 空間：5005² × 4B ≈ 100 MB，符合限制。

技巧總結

1. 座標偏移 +1 統一邊界處理。
2. 二維前綴和模板化，O(1) 區域查詢。
3. 枚舉右下角而非左上角，代碼更簡潔。