链接：

题意：

题目给了个f(x)的定义：F(x) = A_n * 2^n-1 + A_n-1 * 2^n-2 + ... + A₂ * 2 + A₁ * 1，Ai是十进制数位，然后给出a,b求区间[0,b]内满足f(i)<=f(a)的i的个数。

题解：

dp[pos][sum]表示枚举到pos位，后面还需要凑sum的个数

代码：

31 int A, B;32 int a[20];33 int dp[20][MAXN];34 35 int f(int x) {36     if (x == 0) return 0;37     int res = f(x / 10);38     return res * 2 + (x % 10);39 }40 41 int dfs(int pos, int sum, bool limit) {42     if (pos == -1) return sum <= A;43     if (sum > A) return 0;44     if (!limit && dp[pos][A - sum] != -1) return dp[pos][A - sum];45     int up = limit ? a[pos] : 9;46     int res = 0;47     rep(i, 0, up + 1)48         res += dfs(pos - 1, sum + i*(1 << pos), limit && i == a[pos]);49     if (!limit) dp[pos][A - sum] = res;50     return res;51 }52 53 int solve(int x) {54     int pos = 0;55     while (x) {56         a[pos++] = x % 10;57         x /= 10;58     }59     return dfs(pos - 1, 0, true);60 }61 62 int main() {63     ios::sync_with_stdio(false), cin.tie(0);64     int T;65     cin >> T;66     memset(dp, -1, sizeof(dp));67     rep(cas, 1, T + 1) {68         cin >> A >> B;69         cout << "Case #" << cas << ": ";70         A = f(A);71         cout << solve(B) << endl;72     }73     return 0;74 }