HDU 2089不要62
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 57238 Accepted Submission(s): 22392
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
算法分析：
参考：https://blog.csdn.net/wust_zzwh/article/details/52100392
数位DP的入门模板题。就是数位上不能有4也不能有连续的62，没有4的话在枚举的时候判断一下，不枚举4就可以保证状态合法了，所以这个约束没有记忆化的必要，而对于62的话，涉及到两位，当前一位是6或者不是6这两种不同情况我计数是不相同的，所以要用状态来记录不同的方案数。
dp[pos][sta]表示当前第pos位，前一位是否是6的状态，这里sta只需要去0和1两种状态就可以了，不是6的情况可视为同种，不会影响计数。
优化：
第一:memset(dp,-1,sizeof dp);放在多组数据外面。
这一点是一个数位特点，使用的条件是：约束条件是每个数自身的属性，而与输入无关。
具体的：上一题不要62和4，这个约束对每一个数都是确定的，就是说任意一个数满不满足这个约束都是确定，比如444这个数，它不满足约束条件，不管你输入的区间是多少你都无法改变这个数不满足约束这个事实，这就是数自身的属性（我们每组数据只是在区间计数而已，只能说你输入的区间不包含444的话，我们就不把它统计在内，而无法改变任何事实）。
由此，我们保存的状态就可以一直用(注意还有要limit，不同区间是会影响数位在有限制条件下的上限的)
这点优化就不给具体题目了，这个还有进一步的扩展。不过说几个我遇到的简单的约束：
1.求数位和是10的倍数的个数,这里简化为数位sum%10这个状态，即dp[pos][sum]这里10 是与多组无关的，所以可以memset优化，不过注意如果题目的模是输入的话那就不能这样了。
2.求二进制1的数量与0的数量相等的个数，这个也是数自身的属性。
3.。。。。。
还是做题积累吧。搞懂思想！
代码实现：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
int a[20];
int dp[20][2];
int dfs(int pos,int pre,int sta,bool limit)
{if(pos==-1) return 1;if(!limit && dp[pos][sta]!=-1) return dp[pos][sta];int up=limit ? a[pos] : 9;int tmp=0;for(int i=0;i<=up;i++){if(pre==6 && i==2)continue;if(i==4) continue;//都是保证枚举合法性tmp+=dfs(pos-1,i,i==6,limit && i==a[pos]);}if(!limit) dp[pos][sta]=tmp;return tmp;
}
int solve(int x)
{int pos=0;while(x){a[pos++]=x%10;x/=10;}return dfs(pos-1,-1,0,true);
}
int main()
{int le,ri;//memset(dp,-1,sizeof dp);可优化while(~scanf("%d%d",&le,&ri) && le+ri){memset(dp,-1,sizeof dp);printf("%d\n",solve(ri)-solve(le-1));}return 0;
}