数位DP是一类与数字枚举有关的DP问题 通常这类问题是要统计某个区间内符合一些性质的数，具有如下的特征： - 要统计区间[l, r]内满足要求的数，往往可以转换成求[0,r] - [0,l) - 对于求区间[0,n)有通用的方法 - 对于一个小于n的数，从高位到低位一定会出现有一位数字小于n的这一位数字 数位上不能有4也不能有连续的62
#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]); //最后是保证位数边界（limit） } 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; }处理数字的位数：
int f(int num){ int ans; int pos = 0; while(num){ digit[++pos]=num; num=num/10; } return dfs( pos, s , true ); } int dfs(int l, int s, bool jud) { if ( l==-1 ) return s == target_s; if ( !e && ~f[l][s] ) return f[l][s];//（f[l][s]!=-1） int ans = 0; int nex = e ? digit[i] : 9; for (int d = 0; d <= nex; ++d) ans += dfs( l-1 , new_s( s,d ) , e && d==nex ); return jud ? ans : f[l][s] = ans; }