不要62
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 20634 Accepted Submission(s): 7063
Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有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
第一道数位DP
写转移方程 和 对每位DP的时候脑子要十分清醒 不然就是要跪的节奏
题解在代码上了
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
int K[10]={1,2,3,4,4,5,6,7,8,9};
// 0 1 2 3 4 5 6 7 8 9
using namespace std;
int F[11][11];
int n,m;
void YCL()
{
F[0][0]=1;F[1][0]=9;F[1][1]=8;F[1][2]=1; //给F赋初值
for(int i=2;i<=10;i++) //递推求解F
{
//其实完全可以只用F[i][0]这一维就够了 但是为了方便理解还是写出3个
F[i][1]=F[i-1][0]*8-F[i-1][2]; //F[i][1] 表示前i位不存在62不存在4 ,不以2开头的数总数
F[i][2]=F[i-1][0]; //F[i][2] 表示前i位不存在62不存在4 ，以2开头的数的总数
F[i][0]=F[i][1]+F[i][2]; //F[i][0] 表示前i位不存在62不存在4的总数
}
}
int DP(int a)
{ int temp[10];
memset(temp,0,sizeof(temp));
int ans=0;
int tot=0;
int flag=1;
if(a==0){tot=1;temp[tot]=0;} //特判一下0
while(a!=0) //拆分整数
{
temp[++tot]=a%10;
a=a/10;
}
temp[tot+1]=0; //后面的计算中 可能要用到tot+1位（不能有残余值） ，但实际上前面memset已经达成了这个功能
for(int i=tot;i>=1;i--) //对每位进行DP
{
if(flag) //如果之前出现了4或者62 代表后面所有的数已经不可能出现所需要的数了
{ if(i==1) //i==1的时候需要特判处理
{
//（先看完下面的再看这）假设i==1 temp[i]=6 temp[i+1]=6 那么这里计算的位2540-2546; 注释1;
ans+=K[temp[i]];
if(temp[i+1]>6) ans-=1; //删除62
else
if(temp[i+1]==6&&temp[i]>=2) ans-=1; //删除62
}
else
{
//temp={2546} 注释2
//假设i==4 temp[i]=2 temp[i+1]=0 那么这里计算的为0-1999;
//假设i==3 temp[i]=5 temp[i+1]=2 那么这里计算的为2000-2499;
//假设i==2 temp[i]=4 temp[i+1]=5 那么这里计算的为2500-2539;
//此时看注释1 从这里就可以看出为什么i==1 的时候要特判
//因为i==2 i==3 i==4的时候都只计算到 2000-1 2500-1 2540-1 当i==1时不能是2546-1了 所以特判一下
ans+=temp[i]*(F[i-1][0]);
if(temp[i]>4) ans-=F[i-1][0]; //当i==3时 代码的意义是删去2400-2499这一段
if(temp[i+1]>6) ans-=F[i-1][0]; // 删去 x6200-x6299
else
if(temp[i+1]==6&&temp[i]>2) ans-=F[i-1][0]; //删去 x6200-x6299
}
if(temp[i+1]==6&&temp[i]==2||temp[i]==4) flag=0; //若此时出现了 62 或 4 由上面那一段注释2可知 未来的计算中 他们始终会在前方 所以显然不存在解了
}
}
return ans;
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
YCL();
while(cin>>n>>m&&(n||m))
{
if(n>m) swap(n,m);
cout<<(DP(m)-DP(n-1))<<endl;
}
}