不要62 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 64679 Accepted Submission(s): 25710 Problem ...
不要62
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 64679 Accepted Submission(s):
25710
杭州交通管理局經常會擴充一些計程車車牌照，新近出來一個好消息，以後上牌照，不再含有不吉利的數字了，這樣一來，就可以消除個別計程車司機和乘客的心理障礙，更安全地服務大眾。
不吉利的數字為所有含有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 鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2089 題目大意：在n-m中有多少個不含 62 4的數 解題思路： 數位DP。記憶化搜索。可以想到用首碼和來解決問題，具體來說，就是[a,b] = [0,b] - [0,a)。 數位DP，將數字各位（個，十，百，千……）分為單一的數字（例如：654321，將其分成 6 5 4 3 2 1）。分數據，我們需要記錄什麼呢？數字的長度是必須記錄的（在此例中長度len=6），因為我們隨後的搜索需要以長度來作為條件。 運用搜索，可以從兩個方向搜索。一是從最高位，二是從最低位。兩者中我們選擇前者。解釋一下： 因為數據較大，我們要儘可能優化時間，所以要用到記憶化搜索。我們選擇從最高位開始搜索，如果我們遍歷0-9後得到一個答案9，我們存起來，然後當遍歷10-19時 可以直接使用這個答案9，因為他們的過程是相同的。數字擴大之後也是同樣的道理。如果選擇從低位搜索，就做不到這樣的效果。dp意義也就失去了，純暴力。。 先上AC代碼，下麵繼續解釋
#include<stdio.h> #include<string.h> int a,b,dp[20][2],shu[20]; int dfs(int len,bool if6,bool up) { if(len==0) return 1; if(!up&&dp[len][if6]) return dp[len][if6]; //記憶 int cnt=0,maxx=up?shu[len]:9; //迴圈限制 for(int i=0;i<=maxx;i++) { if(i==4||if6&&i==2) //搜索到4時直接跳出不計數，當上一位為6並且這一位為2時跳出不計數 continue ; cnt+=dfs(len-1,i==6,up&&i==maxx); } return up?cnt:dp[len][if6]=cnt; } int solve(int x) { int k=0; memset(shu,0,sizeof(shu)); while(x) { shu[++k]=x%10; x/=10; } return dfs(k,false,true); } int main() { while(scanf("%d%d",&a,&b)!=EOF&&(a+b)) { printf("%d\n",solve(b)-solve(a-1)); } return 0; }View Code
現在解釋一下搜索。len是當前搜索位，if6為上一位是否為6，up為上一位是否是最大值（還是654321，當len=6，up為ture，所以迴圈只能到達i==6；如果len=6，i<6，dfs，那麼up為false，所以迴圈可以到9）.
直觀數字 給定數字235，搜索len=3時，如果迴圈中i=1，那麼下一位可以搜索到9，即從100-190；如果迴圈中i=2，那麼下一位搜索只能迴圈到3，即從200-230。
解釋起來有些困難，理解代碼更容易一點。
因水平有限，只能解釋到這裡了。。。
