不要62

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

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

?

Input 輸入的都是整數(shù)對(duì)n、m（0<n≤m<1000000），如果遇到都是0的整數(shù)對(duì)，則輸入結(jié)束。

?

Output 對(duì)于每個(gè)整數(shù)對(duì)，輸出一個(gè)不含有不吉利數(shù)字的統(tǒng)計(jì)個(gè)數(shù)，該數(shù)值占一行位置。

?

Sample Input 1 100 0 0

?

Sample Output 80

?

Author qianneng

?

Source 迎接新學(xué)期——超級(jí)Easy版熱身賽

?

Recommend lcy???|???We have carefully selected several similar problems for you:??2094?2090?2091?2093?2092? 一道數(shù)位dp，開始想暴力解結(jié)果超時(shí)，然后想先把每個(gè)百位，千位數(shù)求出來(lái)簡(jiǎn)化再暴力，然后發(fā)現(xiàn)太復(fù)雜了，最后百度才想到數(shù)位dp，唉 dp還是沒(méi)入門，看題目的時(shí)候思維完全沒(méi)往那方面想 貼出代碼，代碼當(dāng)中有解析 參考了這位大大 ?http://www.cnblogs.com/wenruo/p/4725005.html #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdio> using namespace std; typedef long long ll; #define maxn 100010 int dp[10][10],d[10]; void init() {dp[0][0] = 1;for(int i=1;i<=7;i++)for(int j=0;j<=9;j++)for(int k=0;k<=9;k++){if(j!=4&&!(j==6&&k==2))dp[i][j] += dp[i-1][k];//把每一位上的下一位有多少個(gè)可以的數(shù)算出來(lái) } } int solve(int num) {int ans = 0,len = 0;while(num){len++;d[len] = num%10;num /= 10;}d[len+1] = 0;for(int i=len;i>=1;i--){for(int j=0;j<d[i];j++){if(d[i+1]!=6||j!=2)ans += dp[i][j];//加上除了d[i]這位數(shù)之外的其他數(shù)的和 }if(d[i]==4||(d[i+1]==6&&d[i]==2))break;//如果d[i]不滿足條件的話就可以直接結(jié)束循環(huán)，不必再加最后一位 }return ans; } int main() {int n,m;init();while(cin >> n >> m){if(!n&&!m)break;printf("%d\n",solve(m+1)-solve(n));//注意m+1，求的是小于m的數(shù)，所以求[0,m]之間的數(shù)時(shí)要加一 }return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/l609929321/p/7044444.html

總結(jié)

以上是生活随笔為你收集整理的hdu2089 不要62 数位dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。