AcWing 1085. 不要62
原题链接
中等
作者:
wangyj
,
2021-01-21 09:45:40
,
所有人可见
,
阅读 281
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int f[35][10];
int DP(int n)
{
if(!n)return 1;
vector<int>num;
while(n)num.push_back(n%10),n/=10;
int ans=0,end=0,i,x,j;
for(i=num.size()-1;i>=0;i--){
x=num[i];
for(j=0;j<x;j++){
if(j==4||end==6&&j==2)continue;
ans+=f[i+1][j];
}
if(x==4||end==6&&x==2)break;
end=x;
if(!i)ans++;
}
return ans;
}
int main()
{
int i,j,k,l,r;
for(i=0;i<=9;i++)if(i!=4)f[1][i]=1;
for(i=1;i<35;i++)for(j=0;j<=9;j++){
if(j==4)continue;
for(k=0;k<=9;k++){
if(k==4||j==6&&k==2)continue;
f[i][j]+=f[i-1][k];
}
}
while(cin>>l>>r,l||r)printf("%d\n",DP(r)-DP(l-1));
return 0;
}