HDU 1455 Sticks：DFS + 剪枝拼木棍問題

HDU 1455 Sticks：DFS + 剪枝拼木棍問題

給定 n 根木棍長度，能否拼成邊長相等的正多邊形（或多條等長木棍）。求最小可能邊長（即最小可行目標長度）。

問題轉化

總長度 sum。目標邊長 L 必須滿足：L ≥ max(棍長)，L 整除 sum。枚舉 L 從 max 到 sum，檢查能否將所有木棍分組，每組和為 L。

DFS 搜索 + 關鍵剪枝

1. 降序排列：大棍優先放置，失敗快。
2. 同長跳過：若某長度棍嘗試失敗，同長度棍同位置必失敗，while (a[i+1]==a[i]) i++;。
3. 首根固定：每條新邊的第一根棍固定選最長的可用棍，避免排列組合爆炸。實現：if (cur_len == 0) break; 在嘗試失敗後退出循環。
4. 精確剪枝：當前邊剩餘長度 < 最小可用棍長 → 回溯。

核心代碼

int n, stick[100], vis[100], target, sides;

bool dfs(int idx, int cur_len, int formed) {
    if (formed == sides) return true; // 所有邊完成
    if (cur_len == target) // 當前邊完成，開始下一邊
        return dfs(0, 0, formed+1);
    int prev = -1;
    for (int i=idx; i target || stick[i] == prev) continue;
        vis[i] = 1;
        if (dfs(i+1, cur_len + stick[i], formed)) return true;
        vis[i] = 0;
        prev = stick[i];
        if (cur_len == 0) break; // 首根棍失敗，無需嘗試其他
        if (cur_len + stick[i] == target) break; // 湊滿失敗，無需嘗試其他
    }
    return false;
}

int main() {
    while (scanf("%d", &n), n) {
        int sum=0, mx=0;
        for (int i=0; i());
        for (target=mx; target<=sum; target++) {
            if (sum % target) continue;
            sides = sum / target;
            memset(vis, 0, sizeof(vis));
            if (dfs(0, 0, 0)) { printf("%d\n", target); break; }
        }
    }
}

測試數據與答案

文中提供大量測試用例及答案，可用於驗證剪枝正確性。

關鍵剪枝解析

複雜度

剪枝後實際搜索極小，n≤64 瞬時通過。屬於 NP 完全問題（多路數分割），剪枝是關鍵。

此題是「DFS + 剪枝」教科書級案例，四大剪枝技巧通用於子集和、分割、排列組合搜索問題。