超級簡單的數位DP....
1 100 0 0
80
#include#include #include #include using namespace std; const int maxn=1000010; int dp[8][3]; int bit[8]; int dfs(int pos,int s,int limit) { if(pos==-1) return s==0||s==1;///目標狀態 if(!limit&&dp[pos][s]!=-1) return dp[pos][s]; int end=limit?bit[pos]:9; int ans=0; for(int i=0;i<=end;i++) { int news=0; if(i==4) news=2; if(i==2&&s==1) news=2; if(i==6) news=1; if(s==2) news=2; ans+=dfs(pos-1,news,limit&&i==end); } if(!limit) dp[pos][s]=ans; return ans; } int solve(int x) { int pos=0; while(x) { bit[pos++]=x%10; x/=10; } return dfs(pos-1,0,1); } int main() { memset(dp,-1,sizeof(dp)); int n,m; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; printf("%d\n",solve(m)-solve(n-1)); } return 0; }