HDU

**题意:** 给出一个范围 $(l,r)$ , 要求计算该范围中 满足 其中连续两位不为62, 并且不包含4 的符合条件个数。 **思路:** 在用数位dp写之前发现自己以前用暴力的方法过去了....（就直接枚举然后除余 4 和 64）所以明明做过一道数位dp的题，却对数位dp毫无印象.. 关于数位dp：在数位上计数用的dp，一般就是要统计一个区间$[l,r]$内满足一些条件数的个数。 这边博客写的很详细：[数位dp入门](https://blog.csdn.net/wust_zzwh/article/details/52100392) 数位dp的记录一般为：$dp[number][state]$ ，即数位个数, 以及不同题目中对应的状态。 一个$solve()$函数处理读入 数的所有位数值，并存于一个 数组中。 然后 $dfs(int space pos,int space pre,int space state,int space limit)$ 记录转移中 枚举的第几个数位，其前一位值， 当前为哪一种状态 ，以及当前位枚举上限。 然后具体细节就看代码了...有注解 code： ```ruby #include #include #include #include using namespace std; int a[20]; int dp[20][2]; //对于一个数 N 找到从1 ~ N 的所有非法情况数目。 //当前位,前导位,状态数,上限 //state表示上一位是否为6 int dfs(int pos,int pre,int state,bool limit){ if(pos==-1) return 1;//表示该数已经被取完 if(!limit && dp[pos][state] != -1) return dp[pos][state]; 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][state] = tmp; return tmp;

}
int solve(int x){
int pos = 0;
//取该数的每一位
while(x){
a[pos++] = x % 10;
x /= 10;
}
//位数，前导初始化-1..
return dfs(pos-1,-1,0,true);
}
int main(){
int l,r;
while(~scanf("%d%d",&l,&r)&&l&&r){
memset(dp,-1,sizeof(dp));
//由于要包含l位置，所以减到l-1
printf("%d ",solve(r)-solve(l-1));
}
}