hdu 4734数位dp（记忆化搜索）

 本题意思非常明确，就是一道数位dp，纯模板题：没什么好说的，直接上代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn = 1<<9;
long long A,B;
int lvalue;
int cnt,limit[10];
int binary_index[10];
int dp[10][10*maxn];
void index_init()///把所有2^n的值保存下来
{
    binary_index[0]=1;
    for(int i=1;i<10;i++)
    {
        binary_index[i]=2*binary_index[i-1];
    }
    memset(dp,-1,sizeof(dp));///也作为一种标记
}
void init()
{
    cnt=0;
    while(B)
    {
        limit[cnt++]=B%10;
        B/=10;
    }
    int cnta=0;
    lvalue=0;
    while(A)
    {
        lvalue+=(A%10)*binary_index[cnta++];
        A/=10;
    }
}
int dfs(int bit,int value,bool flag)
{
    int ans=0;
    if(value<0)
        return 0;
    if(bit<0)
    {
        if(value>=0)
            return 1;
    }
    if(!flag && dp[bit][value]!=-1)///只有当这位没有范围限制的时候才能够用dp[bit][value]
    {
        return dp[bit][value];
    }
    int num = (flag ? limit[bit]:9);
    for(int i=0;i<=num;i++)
    {
        ans+=dfs(bit-1,value-i*binary_index[bit],flag && (i==limit[bit]));///为什么不用dp[bit][value]递推的原因就是有范围限制，如果这次更新了，那么下次还是不能直接用
    }
    if(!flag)///关键的地方，如果没有这一步的话，那么每一个都没有记录，时间复杂度一样
        dp[bit][value]=ans;
    return ans;
}
int main()
{
    int nCase;
    scanf("%d",&nCase);
    index_init();
    for(int t=1;t<=nCase;t++)
    {
        scanf("%I64d%I64d",&A,&B);
        init();
        printf("Case #%d: %d
",t,dfs(cnt-1,lvalue,1));
    }
    return 0;
}