ZOJ 3675 Trim the Nails：指甲刀修剪最小次數 DFS + 剪枝

問題建模

• 指甲寬度 M ≤ 20 毫米，初始全未剪（0）。
• 指甲刀寬度 N ≤ 10，邊緣由 *（好）和 .（壞）組成，如 **..**。
• 可翻轉指甲刀（鏡像對稱）。
• 好邊緣（*）剪除對應位置指甲，壞邊緣（.）保留原狀。
• 求將指甲完全剪平（全 1）的最少操作次數，不可能輸出 -1。

關鍵觀察

1. 左/右邊界：指甲刀最左/右的 * 位置 L, R。只有這兩個位置能「推進」剪切前沿。
2. 狀態表示：fig[1..M]，0=未剪，1=已剪。初始全 0。
3. 操作：選擇當前最左未剪位置 s，對齊指甲刀的 L（正放）或 R（翻轉），將覆蓋範圍內的 * 映射為 1。
4. 遞歸搜索：dfs(fig, s, flip, step)，flip=0/1 表示正放/翻轉。每步嘗試兩種朝向，取最小步數。
5. 剪枝：step ≥ best 直接返回；若指甲刀全壞（L=0）直接輸出 -1。

完整 C++ 實現

#include <bits/stdc++.h>
using namespace std;

int N, M;
string clipperStr;
int clipper[20];          // 1-based: 1=good, 0=bad
int L, R;                 // 最左/右好邊緣位置
int best;
int fig[30];              // 指甲狀態，1-based

void dfs(int pos, bool flipped, int step) {
    if (step >= best) return;          // 剪枝

    // 複製當前狀態
    int nxt[30];
    memcpy(nxt, fig, sizeof(fig));

    // 應用指甲刀
    if (!flipped) {  // 正放：L 對齊 pos
        for (int i = pos, j = L; i <= M && j <= N; ++i, ++j)
            if (!nxt[i]) nxt[i] = clipper[j];
    } else {         // 翻轉：R 對齊 pos
        for (int i = pos, j = R; i <= M && j >= 1; ++i, --j)
            if (!nxt[i]) nxt[i] = clipper[j];
    }

    // 尋找下一個未剪位置
    int nextPos = M + 1;
    for (int i = pos; i <= M; ++i)
        if (!nxt[i]) { nextPos = i; break; }

    if (nextPos == M + 1) {  // 全部剪完
        best = step;
        return;
    }

    // 遞歸：下一步可正放或翻轉
    memcpy(fig, nxt, sizeof(fig));
    dfs(nextPos, false, step + 1);
    dfs(nextPos, true, step + 1);
    memcpy(fig, nxt, sizeof(fig));  // 回溯（實際上這裡不需要，因為傳值或用局部陣列更好）
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> N) {
        cin >> clipperStr >> M;
        fill(clipper, clipper + 20, 0);
        for (int i = 0; i < N; ++i)
            if (clipperStr[i] == '*') clipper[i+1] = 1;

        // 找最左/右好邊緣
        L = 0; for (int i = 1; i <= N; ++i) if (clipper[i]) { L = i; break; }
        R = 0; for (int i = N; i >= 1; --i) if (clipper[i]) { R = i; break; }

        if (L == 0) { cout << -1 << '\n'; continue; }  // 全壞

        best = INT_MAX;
        fill(fig, fig + 30, 0);
        dfs(1, false, 1);  // 從位置1開始，嘗試正放
        dfs(1, true, 1);   // 嘗試翻轉
        cout << best << '\n';
    }
    return 0;
}

代碼優化說明

• 狀態傳值而非引用：dfs 參數改為 array<int,30> fig（C++11）或直接在函數內用局部陣列 nxt，避免手動 memcpy 回溯，代碼更簡潔安全。
• 雙向嘗試：主函數調用兩次 dfs 分別以正放/翻轉起步，覆蓋所有可能序列。
• 複雜度：最壞 O(2^(M/L))，但 M≤20, N≤10 且剪枝極強，實際瞬間通過。

樣例演示

輸入:
8
****..**
4
6
*..
7

輸出:
1
2

Case 1：指甲刀 ****..** 正放一次覆蓋前 4 毫米，剪完。
Case 2：需正放+翻轉各一次。

總結

ZOJ 3675 是典型的「狀態空間小、操作不可逆、貪心失效」題目，適合 DFS + 剪枝。核心建模是「指甲刀左右好邊緣決定推進能力」，狀態僅需記錄「最左未剪位置」與「當前指甲狀態」。掌握此類「一維覆蓋 + 翻轉對稱」建模技巧，可解決許多類似的資源分配/覆蓋優化問題。