hdoj4734（数位dp优化）

题目链接：https://vjudge.net/problem/HDU-4734

题意：定义一个十进制数AnAn-1...A1的value为An*2^n-1+...+A1*2⁰，T组样例(<=1e4)，每组样例给出a、b，求出[0,b]中value小于等于a的value的数的个数。

思路：数位dp，第一能想到将Ai*2^i-1的和作为状态，即dp[len][sum]表示到长度为len的数中value为sum的数的个数，最后判断sum<=value(a)来确定是否满足条件。但是问题来了，我们会发现这样的状态与输入a相关，而输入有1e4组，时间限制为500ms，每次还都要memset(dp)，显然会超时。

　　这个时候就要优化，利用减法，dp[len][sum]表示长度len中value<=sum的数的个数，这一状态性质是所有数共有的性质，与输入a无关，因此可以保存dp的值，而不用memset，最后的结果就是递归到最后一层的sum>=0的数的个数，即value<=value(a)。

AC代码：

#include<cstdio>
#include<cstring>
using namespace std;

int a[10],dp[10][4700],T;

int gets(int x){
    int k=0,ret=0;
    while(x){
        ret+=(1<<k)*(x%10);
        x/=10;
        k++;
    }
    return ret;
}

int dfs(int pos,int sum,bool limit){
    if(pos==-1) return 1;
    if(!limit&&dp[pos][sum]!=-1) return dp[pos][sum];
    int up=limit?a[pos]:9;
    int tmp=0;
    for(int i=0;i<=up;++i){
        int t=sum-(1<<pos)*i;
        if(t<0) continue;
        tmp+=dfs(pos-1,t,limit&&i==a[pos]);
    }
    if(!limit) dp[pos][sum]=tmp;
    return tmp;
}

int solve(int x,int sum){
    int pos=0;
    while(x){
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,sum,true);
}

int main(){
    memset(dp,-1,sizeof(dp));
    scanf("%d",&T);
    for(int i=1;i<=T;++i){
        int a,b,suma;
        scanf("%d%d",&a,&b);
        suma=gets(a);
        printf("Case #%d: %d
",i,solve(b,suma));
    }
    return 0;
}