题意：对于一个数x，将其表示成十进制为(An,An-1...A2,A1)，则F(x) = An*2^(n-1) + A(n-1)*2^(n-2) + ... + A2*2 + A1。给定整数a，b，求F()值不超过F(a)且属于[0,b]的整数有多少个。a,b < 10^9，10000组case。
Ps:这是2013年成都区域赛网络赛的题目。
解法：设数组d[i][j]表示长度为i的数(首位可以为0)中F()值不超过j的数有多少个。具体解法见代码。
tag:数位DP
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-12-14 15:50 4 * File Name: DP-HDU-4734.cpp 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 10 using namespace std; 11 12 #define CLR1(x) memset(x, -1, sizeof(x)) 13 #define CLR(x) memset(x, 0, sizeof(x)) 14 15 int dit_b[20], d[20][10000]; 16 17 int Mypow(int p, int n) 18 { 19 int ret = 1; 20 while (n){ 21 if (n & 1) ret *= p; 22 n >>= 1; 23 p *= p; 24 } 25 return ret; 26 } 27 28 int dit_dev(int x, int* dit) 29 { 30 int ret = 0; 31 while (x){ 32 dit[ret++] = x % 10; 33 x /= 10; 34 } 35 return ret; 36 } 37 38 int cal(int x) 39 { 40 int ret = 0, dit[20]; 41 CLR (dit); 42 int len = dit_dev(x, dit); 43 for (int i = 0; i < len; ++ i) 44 ret += dit[i] * Mypow(2, i); 45 return ret; 46 } 47 48 int rec(int len, int cost, bool flag) 49 { 50 if (len < 0) return 1; 51 52 if (flag){ 53 int &ret = d[len][cost]; 54 if (ret != -1) return ret; 55 ret = 0; 56 57 for (int i = 0; i < 10; ++ i){ 58 int tmp = i * Mypow(2, len); 59 if (tmp <= cost) ret += rec(len-1, cost-tmp, 1); 60 } 61 return ret; 62 } 63 else{ 64 int ret = 0; 65 for (int i = 0; i < dit_b[len]; ++ i){ 66 int tmp = i * Mypow(2, len); 67 if (tmp <= cost) ret += rec(len-1, cost-tmp, 1); 68 } 69 int tmp = dit_b[len] * Mypow(2, len); 70 if (tmp <= cost) ret += rec(len-1, cost-tmp, 0); 71 return ret; 72 } 73 } 74 75 int main() 76 { 77 int a, b, T, test = 0; 78 CLR1 (d); 79 scanf ("%d", &T); 80 while (T--){ 81 scanf ("%d%d", &a, &b); 82 CLR (dit_b); 83 int tmp = cal(a), len_b = dit_dev(b, dit_b); 84 printf ("Case #%d: %d ", ++test, rec(len_b-1, tmp, 0)); 85 } 86 return 0; 87 }