题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4734

题意：我们定义十进制数x的权值为f(x) = a(n)*2^(n-1)+a(n-1)*2(n-2)+...a(2)*2+a(1)*1，a(i)表示十进制数x中第i位的数字。

　　题目给出a，b，求出0~b有多少个不大于f(a)的数

显然这题可以设这样的dp

dp[len][count]表示前len位权值为count的有多少，然后显然的在len==0时return count>=f(a);

但是这样每次Gets数字时都要初始化一下dp然而这题刚好时间要求时500ms而且组数比较多，那么

这样肯定要超时，count经过计算最大只有4599所以设为4600也可以但这样也要超时，于是要优化

一下dp。依旧是dp[len][count]但这时count表示的是钱len位权值不超过count的数有几个，那么只

要一开始初始化一下dp就可以了。

#include <iostream>#include <cstdio>#include <cmath>#include <cstring>using namespace std;const int M = 4600;int dp[10][M] , dig[10] , fat;int dfs(int len , int Fx , int flag , int power) {    if(!len)        return Fx >= 0;    if(Fx < 0)        return 0;    if(!flag && dp[len][Fx] != -1)        return dp[len][Fx];    int t = flag ? dig[len] : 9;    int sum = 0;    for(int i = 0 ; i <= t ; i++) {        sum += dfs(len - 1 , Fx - power * i , flag && i == t , power / 2);    }    if(!flag)        dp[len][Fx] = sum;    return sum;}int Get(int x) {    int sum = 0;    int len = 0;    if(x == 0) {        return 0;    }    int power = 1;    while(x) {        sum += power * (x % 10);        x /= 10;        power *= 2;    }    return sum;}int Gets(int x) {    int len = 0;    if(x == 0) {        dig[++len] = 0;    }    int power = 1;    while(x) {        dig[++len] = x % 10;        x /= 10;        power *= 2;    }    return dfs(len , fat , 1 , power / 2);}int main() {    int t;    int ans = 0;    memset(dp , -1 , sizeof(dp));    scanf("%d" , &t);    while(t--) {        ans++;        int a , b;        scanf("%d%d" , &a , &b);        fat = Get(a);        printf("Case #%d: %d\n" , ans , Gets(b));    }    return 0;}

hdu 4734 F(x)（数位dp+优化）