HDU 1407/1248 暴力枚舉技巧：三平方和與組合優化

HDU 1407：三平方和分解

對給定 n，找非負整數 x≤y≤z 使 x²+y²+z²=n。n ≤ 10000 左右。

三重循環 + 剪枝：

for (int i=1; i*i<=n; ++i)
    for (int j=i; j*j<=n; ++j)
        for (int k=j; k*k<=n; ++k)
            if (i*i + j*j + k*k == n) { output; goto END; }

goto 直接跳出多層循環，簡潔高效。

HDU 1248：組合優化

有 150/200/350 三種包裝，買滿 m 最少剩多少。m ≤ 100000 左右。
三重循環枚舉三種包裝數量，計算剩餘取最小。剪枝條件 i*150 <= m 等大幅減少迭代。

暴力枚舉優化原則

1. 利用對稱性/順序性減少重複（如 i≤j≤k）
2. 循環邊界緊扣約束（i*i <= n 而非 i <= n）
3. 提前剪枝：內層循環條件依賴外層變量
4. goto 或標記變量跳出多層循環
5. 小數據範圍下，暴力往往比複雜算法更快寫、更不易錯

完整代碼示例

// HDU 1407
#include 
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        int x=0,y=0,z=0;
        for (int i=1; i*i<=n; ++i)
            for (int j=i; j*j<=n; ++j)
                for (int k=j; k*k<=n; ++k)
                    if (i*i+j*j+k*k == n) { x=i; y=j; z=k; goto OUT; }
        OUT: printf("%d %d %d\n", x,y,z);
    }
    return 0;
}

// HDU 1248
#include 
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int m, ans=1e9; scanf("%d", &m);
        for (int i=0; i*150<=m; ++i)
            for (int j=0; j*200<=m; ++j)
                for (int k=0; k*350<=m; ++k) {
                    int used = i*150 + j*200 + k*350;
                    if (used <= m) ans = min(ans, m-used);
                }
        printf("%d\n", ans);
    }
    return 0;
}

心得

暴力枚舉不是「無腦嘗試」，而是「在約束條件下精心設計循環邊界與剪枝」。對於中小規模數據，優化得當的暴力往往是工程上的最優解。