digital DP
applicable conditions
This type of topic generally requires a\([l,r]\)The number of numbers in the interval that satisfy the condition, and the answer is generally not related to the size of the number, but to the composition of each of its parts. The range of numbers given in the question is generally large, often between\(10^9\)The above therefore cannot be enumerated violently, and only dynamic programming can be used.
code implementation
utilizationMemorized SearchSimpler and easier to understand.
Searching from the higher to the lower digits of the number, each bit can be\(0-9\). But note that when searching for the first\(i\)bit, if the first\(i-1\)When the bit is already the maximum value, then the current number cannot exceed the maximum value either, i.e. the range is
Thus the memoized search function takes two arguments.
1.\(cur\)Indicates the current location of the first\(cur\)classifier for honorific people
2.\(lim\)preindex\(cur-1\)Whether or not they have all been maximized.as\(lim_{cur+1}==1\), if and only if
Because the title requires\([l,r]\)The number of intervals that satisfy the condition can be found in a similar way to prefix sums since the number satisfies interval additivity. Set\(calc(i)\)indicate\(0-i\)number in the interval, then the answer is\(calc(r)-calc(l-1)\)
\(ACcode\)
\(DFS code\)
int dfs(int x,bool lim){
if(x<=0)return 1;
if(!lim&&f[x]!=-1)return f[x];
int up=lim?a[x]:9;
int ans=0;
for(int i=0;i<=up;i++){
if(i!=4)ans+=dfs(x-1,lim&&(i==up));
}
if(!lim)f[x]=ans;
return ans;
}
Initialization+\(calc\ code\)
int calc(int x){
len=0;
memset(f,-1,sizeof(f));
while(x){
a[++len]=x%10;
x/=10;
}
return dfs(len,1);
}