【筆記】數位DP

  • Digit DP,計數用的DP。
  • 【用途】查找 [0, x] 區間內,符合條件的個數。用非常少的狀態(處理每個digit)來得到需要的下一個狀態,避免疊代每個數字衍生的重複計算。
  • 【範例】HDU 2089 不要62題解
  • dp[7][2][2]:
    • 第一個維度 pos:目前處理的位數。數字 0<n≤m<1000000,最多七位數。
    • 第二個維度 pre:紀錄前一位數是否為 6 (true/false)
    • 第三個維度 lim:是否到達上限 (true/false)。例如 n = 655,假如最高位數是 6 (達上限),則第二位數最大只能是 5。如果最高位數小於 6 (未達上限),則第二位數最大可以是 9。
  • 函式 dfs( ):從高位數往低位數檢查。
  • 函式 solve( ):計算數字的位數,然後呼叫 dfs( ),初始狀態 pre = false, lim = true。
  • 題目要計算 [n, m]區間內符合條件的個數,因此答案是solve(m) – solve(n-1)。
  • 【更多練習】Codeforces 1245F. Daniel and Spring Cleaning題解
#include <iostream>
#include <cstring>
using namespace std;

int n, m, a[7], dp[7][2][2];

int dfs(int pos, int pre, int lim){
    //遞迴終止條件
    if (pos == -1) return 1; //檢查完所有位數,得到一組解
    if (dp[pos][pre][lim] != -1) return dp[pos][pre][lim];
    //ub:這個位數的上限值
    int ub = lim ? a[pos] : 9;
    int ans = 0;
    for (int i = 0; i <= ub; i++){
        if (i == 4) continue; //不能有4
        else if (pre && i == 2) continue; //不要62
        ans += dfs(pos-1, i==6, lim && i==a[pos]);
    }
    dp[pos][pre][lim] = ans;
    return ans;
}

int solve(int x){
    int cnt = 0;
    memset(dp, -1, sizeof(dp));
    //cnt:數字x有幾位數
    while (x){
        a[cnt] = x % 10;
        x /= 10;
        cnt++;
    }
    return dfs(cnt-1, 0, 1);
}

int main() {
    while (cin >> n >> m){
        if (n == 0 && m == 0) break;
        cout << solve(m) - solve(n-1) << "\n";
    }
}
分享本文 Share with friends