HDU 4734: F(x) （数位DP）

总结：

去数字那维的方法，就是改成循环里面枚举当前位（之前的做法是枚举下一位）

抽象出口，可以从前一个有意义的状态来推导出其意义。

类型：

数位DP

题意：

F(x) = A _n * 2 ^n-1 + A _n-1 * 2 ^n-2 + ... + A ₂ * 2 + A ₁ * 1.问[0,B]之间满足F(x) <= F(A)的x的数量。 (0 <= A,B < 10 ⁹)

思路：

第一次尝试去掉d（数字）那维。

去掉之后找回来，实际上采用的是枚举当前位的方法。

去掉那维之后，状态的意思也发生了一定的改变，导致dfs里面的写法也有一定的改变。（num[i-1] ==> num[i]）

定义：dp[i][f] 表示所有i位数中（含前导0），F() <= f  的数的数量。

那么

dp[i][f] = sum(dp[i-1][f-j*2^i-1])   (j = 0~9(end))

出口：

f<0: return 0;

(无论怎么样也不可能有一个数的F（） 是负的）

i == 0: return 1;

（理解1：[抽象这个无意义的状态] i==0时，是0位数，0位数并不存在，但 应该 其F() == 0，所以只要是正的f，都满足）

（理解2：[从前一个有意义的状态考虑] i==0是由i==1这个状态过来的。在i==1时，枚举每个数，然后f减去那个数的权值，如果之后比0大，就说明那个数可取。汇和到i==0就是直接return 1）

代码：

#include <cstdio>
#include <cstring>

int dp[12][10000];
int num[30];

int getf(int x) {
    int ans = 0;
    int len = 0;
    while (x) {
        ans += (x%10)*(1<<(len));
        x/=10;
        len++;
    }
    return ans;
}

int dfs(int i, int f, bool isQuery) {
    if (f < 0) return 0;
    int &nowdp = dp[i][f];
    if (!isQuery && ~nowdp) return nowdp;
    if (i == 0) {
        return 1;
    }
    int end = isQuery?num[i]:9; /*这里不一样哦！*/
    int ans = 0;
    for (int j = 0; j <= end; j++) {
        int nextf = f-j*(1<<(i-1)); /*这里不一样哦！*/
        ans += dfs(i-1, nextf, isQuery && j==end);
    }
    if (!isQuery) nowdp = ans;
    return ans;
}

int cal(int a, int x) {
    int len = 0;
    if (x == 0) {
        num[++len] = 0;
    } else {
        while (x) {
            num[++len] = x%10;
            x/=10;
        }
    }
    return dfs(len, getf(a), true); /*这里不一样哦！*/
}

int main() {
    int t;
    scanf("%d", &t);
    memset(dp, -1, sizeof(dp));
    int cas = 1;
    while (t--) {
        printf("Case #%d: ", cas++);
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d
", cal(a,b));
    }
    return 0;
}