題目:?http://acm.hdu.edu.cn/showproblem.php?pid=2089

不要62

Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 30895????Accepted Submission(s): 10898

Problem Description 杭州人稱那些傻乎乎粘嗒嗒的人為62（音：laoer）。
杭州交通管理局經常會擴充一些的士車牌照，新近出來一個好消息，以后上牌照，不再含有不吉利的數字了，這樣一來，就可以消除個別的士司機和乘客的心理障礙，更安全地服務大眾。
不吉利的數字為所有含有4或62的號碼。例如：
62315 73418 88914
都屬于不吉利號碼。但是，61152雖然含有6和2，但不是62連號，所以不屬于不吉利數字之列。
你的任務是，對于每次給出的一個牌照區間號，推斷出交管局今次又要實際上給多少輛新的士車上牌照了。

?

Input 輸入的都是整數對n、m（0<n≤m<1000000），如果遇到都是0的整數對，則輸入結束。

?

Output 對于每個整數對，輸出一個不含有不吉利數字的統計個數，該數值占一行位置。

?

Sample Input 1 100 0 0

?

Sample Output 80

?

Author qianneng

?

Source 迎接新學期——超級Easy版熱身賽?

?

Recommend lcy???|???We have carefully selected several similar problems for you:??2090?2091?2093?2092?2086? 題解： 數位dp 具體見這個PDF ?: ?http://wenku.baidu.com/view/9de41d51168884868662d623.html?from=search 舉個例子： 比如當前要計算的數是456，那么 ? ? ? ? 4 ? ?5 ? ?6 ? ? ? ? — ? — ? —? 當第一位枚舉范圍為（0～3）時，我們預處理的F[][]是可以直接加的，因為后兩位取任何值（0～9）都滿足小于456。 然后考慮第一位為4時，第二位枚舉范圍為（0～4）時，f[][]也是可以直接加。 接著考慮第一位為4，第二位為5時，第三位在（0～5）都是可以直接加f[][]的。 然后我們發現當第一位為4，第二位為5，第三位為6的情況沒有考慮，但是循環已經結束了。所以我們要計算的數必須先＋1。 代碼中有詳細解釋。 1 #include<bits/stdc++.h> 2 using namespace std; 3 int F[10][12],digit[10]; 4 int read() 5 { 6 int s=0,fh=1;char ch=getchar(); 7 while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();} 8 while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();} 9 return s*fh; 10 } 11 void GetF() 12 { 13 int i,j,k; 14 memset(F,0,sizeof(F));//F[i][j]為位數為i位,以j開頭的方案數 15 F[0][0]=1; 16 for(i=1;i<=7;i++)//枚舉每一位 17 { 18 for(j=0;j<=9;j++)//枚舉第i位 19 { 20 if(j==4)continue; 21 for(k=0;k<=9;k++)//枚舉第i-1位 22 { 23 if(k==2&&j==6)continue; 24 F[i][j]+=F[i-1][k]; 25 } 26 } 27 } 28 } 29 int Calc(int num) 30 { 31 int len=0,ans=0,i,j; 32 memset(digit,0,sizeof(digit));//必須要清空 33 while(num!=0){digit[++len]=num%10;num/=10;}//分離num的每一位 34 for(i=len;i>=1;i--)//從高位開始枚舉 35 { 36 for(j=0;j<=digit[i]-1;j++)//枚舉每一位可以直接加F[][]的數字,可以發現最后一位也是枚舉到digit[]-1的,所以每一位的最大值組成的數字即原數字num沒有被枚舉到,所以傳入Calc()前要先加1 37 { 38 if(j==4||(digit[i+1]==6&&j==2))continue; 39 ans+=F[i][j]; 40 } 41 if(digit[i]==4||(digit[i+1]==6&&digit[i]==2))break; 42 } 43 return ans; 44 } 45 int main() 46 { 47 int n,m; 48 GetF(); 49 while(1) 50 { 51 n=read();m=read();if(n==0&&m==0)break; 52 printf("%d\n",Calc(m+1)-Calc(n));//Calc(k)求出的是0~k-1中符合的方案數,所以傳進去前要+1 53 } 54 fclose(stdin); 55 fclose(stdout); 56 return 0; 57 }

?

轉載于:https://www.cnblogs.com/Var123/p/5383539.html

總結

以上是生活随笔為你收集整理的Hdu 2089-不要62 数位dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。