BZOJ 1088 [SCOI2005] 掃雷 Mine：一維 DP / 狀態枚舉

n×2 棋盤，第一列可能有雷，第二列無雷但顯示周圍 8 連通雷數（實際只受第一列同行、上下行影響）。給第二列數字，求第一列雷分布方案數。n ≤ 10000。

關鍵觀察

第二列第 i 行數字 l2[i] 等於第一列 i-1, i, i+1 三行雷數之和（邊界視為 0）。即：

l2[i] = l1[i-1] + l1[i] + l1[i+1]   (l1[0]=l1[n+1]=0)

這是一個線性遞推關係。若知道 l1[1] 和 l1[2]，可唯一推導出所有 l1[i]。

枚舉起始狀態

l1[1] 只能是 0 或 1（有雷/無雷）。
由 l2[1] = l1[1] + l1[2] 得 l1[2] = l2[1] - l1[1]。
l1[2] 必須是 0 或 1，否則該起始無效。
因此 l1[1] 只有 0、1 兩種可能，且受 l2[1] 限制：

• l2[1]=0 → l1[1]=0, l1[2]=0
• l2[1]=1 → l1[1]=0, l1[2]=1 或 l1[1]=1, l1[2]=0
• l2[1]=2 → l1[1]=1, l1[2]=1

最多 2 種起始，對每種起始向下遞推：

for i = 2..n:
    l1[i+1] = l2[i] - l1[i] - l1[i-1]
    if l1[i+1] not in {0,1}: 方案無效，break
最後檢查 l1[n+1] == 0（虛擬第 n+1 行必無雷）

完整代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10010;
int l1[MAXN], l2[MAXN];

bool check(int n) {
    for (int i = 2; i <= n; ++i) {
        l1[i+1] = l2[i] - l1[i] - l1[i-1];
        if (l1[i+1] != 0 && l1[i+1] != 1) return false;
    }
    return l1[n+1] == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) cin >> l2[i];
        int ans = 0;
        for (int first = 0; first <= l2[1]; ++first) {  // 枚舉 l1[1]
            fill(l1, l1 + n + 2, 0);
            l1[1] = first;
            l1[2] = l2[1] - first;
            if (l1[2] == 0 || l1[2] == 1) {
                if (check(n)) ++ans;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

• 時間：O(n)，常數極小（最多 2 次遍歷）
• 空間：O(n)

正確性證明

方程組：

l2[1] = l1[1] + l1[2]
l2[i] = l1[i-1] + l1[i] + l1[i+1]  (2≤i≤n)
l1[0] = l1[n+1] = 0

這是三對角線性系統，自由度為 1（由 l1[1] 決定）。枚舉 l1[1]∈{0,1} 窮盡所有可能解，檢查約束 l1[i]∈{0,1} 及邊界 l1[n+1]=0 即得合法方案數。

擴展：寬度為 m 的一般情況

狀態壓縮 DP：每行 m 列，狀態 2^m，轉移檢查上兩行約束。m≤8 可行，m=2 退化為本題 O(n) 解法。

此題展示了「利用問題結構將指數狀態降為常數」的典型技巧，屬於「掃雷數字反推雷分布」系列入門題。