1 dp[i][j] 可以直接求 <f(a) 是数目 但是时间被卡住了 dp[i][j]都要被初始化
2 dp[i][j] 求到i <j 的数目
#include <iostream> #include<string.h> #include<stdio.h> using namespace std ; #define ll long long int dig[12]; int jud; int z[12]; int dp[12][30000]; void calc(int a) //dp[i][j] 第i位 小于j多少个 { int cnt=0; jud=0; while(a) { dig[cnt++]=a%10; a=a/10; jud=jud+dig[cnt-1]*z[cnt-1]; } } int dfs(int len,int sum,int e) { if(len<0) return sum>=0; if(sum<0) return 0; if(!e&&dp[len][sum]!=-1) return dp[len][sum]; int u=e?dig[len]:9; int ans=0; for(int i=0;i<=u;i++) ans+=dfs(len-1,sum-i*z[len],e&&(i==u)); if(!e) dp[len][sum]=ans; return ans; } int calc1(int n) { int cnt=0; while(n) { dig[cnt++]=n%10; n=n/10; } return dfs(cnt-1,jud,1); } int main() { int t,ca; scanf("%d",&t); z[0]=1; for(int i=1;i<=11;i++) z[i]=z[i-1]*2; ca=1; memset(dp,-1,sizeof(dp)); while(t--) { int a,b; scanf("%d%d",&a,&b); calc(a); printf("Case #%d: %d ",ca++,calc1(b)); } return 0; }