题意：(hdu 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)的数

#include <stdio.h>

#include <string.h>

int mx[];

int dp[][];

/*

　　<数位DP>

　　　　所谓数位DP就是基于考虑数字的每一位来转移的DP。

　　　　例如求比456小的数，可以这么考虑，

　　　　　　　　4          5               6

　　　　　　　  4　        5             (0~6)

　　　　　　　　4          (0~4)         (0~9)

　　　　　　　　(0~3)      (0~9)         (0~9)

　　　　然后我们就可以考虑用dp[len][pre]表示长度为len，以pre开头的符合条件的数的个数。

　　　　这样就可以得到转移方程了。

　　而对于这道题，我们可以用dp[len][pre]表示长度为len且权值不大于pre的数。

　　这道题用记忆化搜索，除边界条件外记录dp[len][pre]的值，下一次发现以前已经计算过了就可以直接return；

　　初值：dp[len][pre] = 0; 

　　　　　dfs(len, pre, flag)表示求长度为len，不超过pre的所有符合条件的值。其中flag是用来控制边界的。

　　　　　dfs过程中当深搜的边界，发现len < 0，pre >=0 的时候就返回1.

*/

int dfs(int len, int pre, bool flag)

{

    if ( len <  ) return pre >=;

    if ( pre <  ) return ;

    if ( !flag && dp[len][pre] != -) return  dp[len][pre];

    int end = flag?mx[len]:;

    int ans = ;

    int i;

    for( i = ; i <= end; i++)

    {

        ans += dfs(len-, pre- i*(<<len), flag&&i==end);

    }

    if( !flag )dp[len][pre] = ans;

    return ans;

}

int f(int x)

{

    int ans = ;

    int tmp = ;

    while( x )

    {

       ans += (x%)*tmp;

       tmp = tmp*;

       x = x/;

    }

    return ans;

}

int cal(int a, int b)

{

    int tmp = ;

    while( b )

    {

       mx[ tmp++ ]= b%;

       b = b/;

    }

    return dfs(tmp - , f(a),  true );

}

int main()

{

    int t;

    int a,b;

    scanf("%d", &t);

    memset(dp, 0xff, sizeof(dp));

    for(int i = ; i <= t; i++ )

    {

        scanf("%d%d",&a, &b);

        printf("Case #%d: %d\n", i, cal(a,b));

    }

    return ;

}