题意: 给出一个范围 \((l,r)\) , 要求计算该范围中 满足 其中连续两位不为62, 并且不包含4 的符合条件个数。思路: 在用数位dp写之前发现自己以前用暴力的方法过去了....（就直接枚举然后除余 4 和 64）所以明明做过一道数位dp的题，却对数位dp毫无印象.. 关于数位dp：在数位上计数用的dp，一般就是要统计一个区间\([l,r]\)内满足一些条件数的个数。 这边博客写的很详细：数位dp入门 数位dp的记录一般为：\(dp[number][state]\) ，即数位个数, 以及不同题目中对应的状态。 一个\(solve()\)函数处理读入 数的所有位数值，并存于一个 数组中。 然后 \(dfs(int \space pos,int \space pre,int \space state,int \space limit)\) 记录转移中 枚举的第几个数位，其前一位值， 当前为哪一种状态 ，以及当前位枚举上限。 然后具体细节就看代码了...有注解 code：
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> 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\n",solve(r)-solve(l-1)); } }转载于:https://www.cnblogs.com/Tianwell/p/11411422.html
