HDU 4734 F(x)：數位 DP 求滿足加權和條件的數字個數

題目大意

定義 F(x) = Σ A_i * 2^{i-1}，其中 x 的十進制位為 A_n ... A_1（低位權重小）。給定 A, B，求 [0, B] 中有多少 i 滿足 F(i) ≤ F(A)。

數位 DP 狀態設計

dp[pos][sum]：處理到第 pos 位（從低位向高位，pos=0 為個位），已確定的低位貢獻總和為 sum，滿足條件的方案數。
轉移：枚舉當前位 d (0..9)，新和 sum + d * 2^{pos}，若 ≤ 目標值則遞歸 pos+1。
記憶化：flag 表示是否受上界 B 限制。

C++ 代碼

#include 
using namespace std;
typedef long long LL;
int bit[20], p2[20];
LL dp[20][6000]; // 最大和：9*(2^10-1) ≈ 9000，開 6000 足夠
int target;

LL dfs(int pos, int sum, bool limit) {
    if (pos == -1) return 1; // 處理完所有位
    if (!limit && dp[pos][sum] != -1) return dp[pos][sum];
    int up = limit ? bit[pos] : 9;
    LL ans = 0;
    for (int d = 0; d <= up; ++d) {
        int nsum = sum + d * p2[pos];
        if (nsum > target) continue; // 剪枝
        ans += dfs(pos-1, nsum, limit && d==up);
    }
    if (!limit) dp[pos][sum] = ans;
    return ans;
}

LL solve(LL x) {
    int len = 0;
    if (x == 0) bit[len++] = 0;
    while (x) { bit[len++] = x%10; x/=10; }
    return dfs(len-1, 0, true);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    p2[0] = 1;
    for (int i = 1; i < 20; ++i) p2[i] = p2[i-1] * 2;
    memset(dp, -1, sizeof(dp));
    int T; cin >> T;
    for (int tc = 1; tc <= T; ++tc) {
        LL A, B; cin >> A >> B;
        // 計算 F(A)
        target = 0; int tmp = A, pos = 0;
        while (tmp) { target += (tmp%10) * p2[pos++]; tmp/=10; }
        LL ans = solve(B);
        cout << "Case #" << tc << ": " << ans << '\n';
    }
    return 0;
}

關鍵點

• 權重 2^{pos} 快速增長，最大和 9 * (2^{10}-1) = 9207，DP 表 dp[20][10000] 足夠。
• pos=-1 為遞歸出口，表示所有位處理完，返回 1 種方案。
• limit 標誌控制是否受 B 的對應位上界約束。
• 剪枝 nsum > target 大幅減少狀態。

總結

HDU 4734 是「數位 DP + 自定義加權和」的典型題。核心模板：位分解 + 狀態為累積權值和 + 記憶化遞歸 + 上界限制標誌。同套路解決 HDU 3555、Codeforces 數位 DP 計數問題。