网址：https://vjudge.net/problem/HDU-4734
定义函数$f(x)$，给出$a，b$，求范围$0$至$b$中有多少数不大于$f(a)$。
数位dp板子题，记录状态的时候就用$f(a)$和sum比较，sum过大了直接返回$0$，其他的正常记录即可，本题时限少，如果每一次都memset会TLE，由于数位dp的dp数组的内容和输入无关（本题数位的模不变，若数位的模改变就需要重新memset），保存的状态可以一直使用，所以只需memset一次。这样子就可以AC。
AC代码：
#include <bits/stdc++.h>
using namespace std;
int dp[10][5000],a[10];
int all;
int dfs(int pos,int sum,bool lim)
{
if(pos==-1)
return sum<=all;
if(all<sum)
return 0;
if(!lim&&dp[pos][all-sum]!=-1)
return dp[pos][all-sum];
int ans=0;
int res=lim?a[pos]:9;
for(int i=0;i<=res;++i)
ans+=dfs(pos-1,sum+i*(1<<pos),lim&&i==a[pos]);
if(!lim)
dp[pos][all-sum]=ans;
return ans;
}
int f(int x)
{
int ans=0,pos=1;
while(x)
{
ans+=(x%10)*pos;
pos<<=1;
x/=10;
}
return ans;
}
int solve(int x)
{
int pos=0;
while(x)
{
a[pos++]=x%10;
x/=10;
}
return dfs(pos-1,0,true);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,a,b;
cin>>n;
memset(dp,-1,sizeof(dp));//状态可以一直使用，除非数位进制变化
for(int i=1;i<=n;++i)
{
cin>>a>>b;
all=f(a);
cout<<"Case #"<<i<<": "<<solve(b)<<endl;
}
return 0;
}
原文：https://www.cnblogs.com/Aya-Uchida/p/11219870.html