不要62 時間限制：1sec 記憶體限制：3MB 題目描述 杭州人稱那些傻乎乎粘嗒嗒的人為62（音：laoer）。 杭州交通管理局經常會擴充一些計程車車牌照，新近出來一個好消息，以後上牌照，不再含有不吉利的數字了，這樣一來，就可以消除個別計程車司機和乘客的心理障礙，更安全地服務大眾。不吉利的數字為所有含有 ...
不要62
時間限制：1sec
記憶體限制：3MB
題目描述
杭州人稱那些傻乎乎粘嗒嗒的人為62（音：laoer）。
杭州交通管理局經常會擴充一些計程車車牌照，新近出來一個好消息，以後上牌照，不再含有不吉利的數字了，這樣一來，就可以消除個別計程車司機和乘客的心理障礙，更安全地服務大眾。不吉利的數字為所有含有4或62的號碼。例如：
62315 73418 88914
都屬於不吉利號碼。但是，61152雖然含有6和2，但不是62連號，所以不屬於不吉利數字之列。
你的任務是，對於每次給出的一個牌照區間號，推斷出交管局今次又要實際上給多少輛新計程車車上牌照了。
輸入
輸入的都是整數對n、m（0<=n<=m<2147483647），如果遇到都是0的整數對，則輸入結束。
輸出
對於每個整數對，輸出一個不含有不吉利數字的統計個數，該數值占一行位置。
樣例輸入
1 100
0 0
樣例輸出
80
提示
數位DP
一看，是沒有什麼問題，不看記憶體限制，打表都能過。
只要開一個數組存，打表就過了。
多簡單的事情，是吧。
只要大約500000的數組。
但是它正好把這個給卡了。
其實也不是沒有辦法。
但很難AC。
所以咱們就只能用數位DP做。
因為題目叫我們用數位DP做啊。
#include<bits/stdc++.h> using namespace std; int dp[15][10]; void init(){ memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=11;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]; } } } } int solve(int n){ int dight[15]; int len=0,ans=0; while(n!=0){ dight[++len]=n%10;n/=10; } dight[len+1]=0; for(int i=len;i>=1;i--){ for(int j=0;j<dight[i];j++){ if(j!=4&&!(dight[i+1]==6&&j==2))ans+=dp[i][j]; } if(dight[i]==4||(dight[i]==2&&dight[i+1]==6))break; } return ans; } int main(){ init(); int l,r; while(1){ scanf("%d%d",&l,&r); if(l+r==0)break; printf("%d\n",solve(r+1)-solve(l)); } return 0; }
代碼雖然不是我想的，但貌似很簡單的樣子。
