题目大意：定义f（x），并给出a和r，问在（0，r）有几个数的f（x）值小于等于f（a）；
题目解析：定义dp[i][j]表示枚举到第i位，j表示f（a）与当前和的差值；
AC代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> using namespace std; int dp[12][10010],n,m,num[12],all; int f(int x) { if(x==0) return 0; int ans=f(x/10); return ans*2+x; } int dfs(int pos,int sum,bool limit) { if(pos==-1) return sum<=all; if(sum>all) return 0; if(!limit&&dp[pos][all-sum]!=-1) return dp[pos][all-sum]; int u=limit?num[pos]:9; int ans=0; for(int i=0;i<=u;i++) { ans+=dfs(pos-1,sum+i*(1<<pos),limit&&i==num[pos]); } if(!limit) return dp[pos][all-sum]=ans; return ans; } int cal(int x) { int pos=0; while(x) { num[pos++]=x; x/=10; } return dfs(pos-1,0,true); } int main() { memset(dp,-1,sizeof(dp)); int cas,c=1; scanf("%d",&cas); while(cas--) { int u; scanf("%d",&u); all=f(u); scanf("%d",&m); printf("Case #%d: %d\n",c++,cal(m)); } }