HDU Bomb：數位 DP 統計包含「49」的數字個數

問題描述

給定正整數 n，求 1 到 n 中包含子串 "49" 的數字個數。多組測試數據。

數位 DP 核心思想

數位 DP 是處理「數字區間內滿足特定性質的數的個數」的通用技術。核心狀態：

• pos：當前處理到第幾位（從高位到低位）
• last：上一位的數字（0-9，初始可設為 0 或特殊值）
• tight（p）：前綴是否已經小於 n 的對應前綴（0=相等，1=已小）
• has49（cur）：是否已經出現過 "49"

狀態轉移邏輯

枚舉當前位填 0-9：

• 若 tight==0（前綴相等），當前位上限為 n 的該位數字；否則上限為 9。
• 若 last==4 且 當前位==9，則 has49 變為 true。
• 遞歸到下一位，更新 last、tight、has49。

代碼實現 (C++)

#include 
using namespace std;
typedef long long ll;

const int MAXL = 20;  // 足夠 64 位整數
ll dp[MAXL][10][2][2];
int vis[MAXL][10][2][2], timer;
string s;
int len;

ll dfs(int pos, int last, int tight, int has49) {
    if (pos == len) return has49;  // 到達末位，若已含 49 計 1
    ll& res = dp[pos][last][tight][has49];
    if (vis[pos][last][tight][has49] == timer) return res;
    vis[pos][last][tight][has49] = timer;
    res = 0;
    int up = tight ? 9 : s[pos] - '0';
    for (int d = 0; d <= up; ++d) {
        int ntight = tight || (d < up);
        int nhas49 = has49 || (last == 4 && d == 9);
        res += dfs(pos + 1, d, ntight, nhas49);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        cin >> s;
        len = s.size();
        ++timer;
        cout << dfs(0, 0, 0, 0) << '\n';
    }
    return 0;
}

關鍵細節

1. 前導零處理：本題數字從 1 開始，無前導零干擾。若包含 0，需額外狀態標記「是否還在前導零階段」。
2. 記憶化：使用 vis + timer 避免多測試用例間 memset 開銷。
3. 狀態壓縮：last 只需 0-9，tight 和 has49 均為 0/1，狀態總數極小（~20×10×2×2=800）。

複雜度

• 時間：O(位數 × 10 × 2 × 2) ≈ O(800) 每查詢，極快。
• 空間：O(800)。

舉一反三

同類問題：統計包含 "13"、"666"、或滿足「相鄰數字差 ≥ 2」等性質的數字個數，只需修改 nhas49 的判斷邏輯即可。