这道题还是关于数位DP的板子题
数位DP有一个显著的特征，就是求的东西大概率与输入关系不大，理论上一般都是数的构成规律
然后这题就是算一个( F(A) )的公式值，然后求( left [ 0 , B ight ] )区间内( F(x) )不大于( F(A) )的数的个数
所以由数据范围很容易得到计算出最大值不会超过4600
然后我们设状态( dp[10][4600][4600] )表示不同( F(A) )取值下的第( pos )个位置的值总和为 ( sumx )的 数的个数
显然会MLE
这时候可以用减法转换状态
用( dp[10][4600] )表示到了第( pos )个位置，还要凑( sumx )的值的数的个数
然后就可以发现一个现象，这个状态与( F(A) )无关的
然后就可做了
注意一个事情，就是求的是不大于( F(A) )的数的个数
所以最后( sumx ge 0 )就是合法状态了
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; int dp[10][4600],a[10]; int dfs(int pos,int limit,int state){ if(state<0) return 0; if(pos==-1){ return state>=0; } if(!limit&&dp[pos][state]!=-1) return dp[pos][state]; int mid=0,up=limit?a[pos]:9; for(int i=0;i<=up;i++){ if((i<<(pos))<=state) mid+=dfs(pos-1,limit&&i==a[pos],state-(i<<(pos))); } if(!limit) dp[pos][state]=mid; return mid; } int solve(int A,int x){ int fa=0,cona=0; while(A){ fa+=((A%10)<<(cona)); A/=10; cona++; } int con=0; memset(a,0,sizeof(a)); while(x){ a[con]=x%10; x/=10; con++; } return dfs(con-1,true,fa); } int main(){ int T; memset(dp,-1,sizeof(dp) ); scanf("%d",&T); for(int i=1;i<=T;i++){ int A,B; scanf("%d %d",&A,&B); printf("Case #%d: %d ",i,solve(A,B)); } return 0; }