HDU 2089 不要62 （数位Dp）

传送门
数位(Dp)模板题，也是我的第一道数位(Dp)题。
感觉数位(Dp)虽然细节比较多，但是确非常套路
而且考的题都比较裸，所以根据题意直接套模板就行

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
int low,high;
int f[20][20],a[20];

int dfs(int pos,int pre,int limit){
	//注意如果当前搜索状态是被限制的话(limit==1)
	//说明当前处于特殊情况，不能 
	if(pos==-1) return 1; //如果pos到达了-1位说明找到一种情况 
	if(!limit && f[pos][pre]!=-1) return f[pos][pre];
	//注意limit如果为真时不可直接使用记忆化数组中的值 
	int up=limit ? a[pos]:9; //本位枚举的上界 
	int temp=0;
	for(int i=0;i<=up;i++){
		if(i==4 || i==2&&pre==6) continue; //由题意可知 
		temp+=dfs(pos-1,i,limit && i==a[pos]); //注意limit的变化方法 
	}
	if(!limit) f[pos][pre]=temp; //要不要更新数组同样取决于limit 
	return temp;
}

int solve(int x){
	int pos;
	for(pos=0;x;pos++,x/=10) 
		a[pos]=x%10;
	//将要求的数拆分出来，可以是任意进制的数，这里是10进制 
	return dfs(pos-1,0,1);
}

int main(){
	while(~scanf("%d%d",&low,&high)&&low+high){
		memset(f,-1,sizeof(f));
		printf("%d
",solve(high)-solve(low-1)); //求区间中的数固定方法 
	}
	return 0; 
}