HDU 4734(数位dp之memset优化)

常规想：dp[pos][sum],这状态是基本的。a是题目给定的，f(a)最大也就4600的样子，如果用memset优化，需要加一维dp[pos][4600][4600]来存f(a)的不同值。这个数组显然不合法。这个时候就要用减法了，dp[pos][sum]是枚举到pos位，小于等于sum的个数，这个状态是和a无关的可以用memset优化。
这道题没有直接按照题目要求设置dp，而是进行了优化，使得多组样例都能用，这一点是一个数位特点，使用的条件是：约束条件是每个数自身的属性，而与输入无关。

#include<bits/stdc++.h>
using namespace std;
int all;
int f(int x){
    if(x==0) return 0;
    int res=f(x/10);
    return res*2+(x%10);
}
int a[10];
int dp[10][100005];
int dfs(int pos,int sum,bool limit)
{
    if(pos==-1) return all-sum>=0;
    if(all-sum < 0) return 0;
    if(!limit && dp[pos][all-sum]!=-1) return dp[pos][all-sum];
    int res=0;
    for(int i=0;i<=(limit?a[pos]:9);++i)
    {
        res+=dfs(pos-1,sum+(i<<pos),limit&&i==a[pos]);
    }
    if(!limit) dp[pos][all-sum]=res;
    return res;
}

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

int main(){
    int t,cas=0;
    scanf("%d",&t);
    memset(dp,-1,sizeof(dp));
    while(t--)
    {
        int a,ri;
        scanf("%d%d",&a,&ri);
        all=f(a);
        printf("Case #%d: %d\n",++cas,solve(ri));
    }
    return 0;
}