- 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";
}
}
Post Views (since April 2021) : 925