简单数位dp
数位dp最重要的还是要理解模板的原理,理解数位dp的原理,理解题目的做法,套模板不一定能解决所有问题,反而大概率会有一些细节出错而无法想到
#include<bits/stdc++.h> #define ll long long using namespace std; int a,b,num[11],len; int f[11][11]; int dfs(int pos,bool lmt,bool led,int lst){ if(pos==0)return 1; if(!lmt && !led && f[pos][lst]!=-1)return f[pos][lst]; int top=lmt?num[pos]:9; int ans=0; // ans+=dfs(pos-1,lst==num[pos],led,lst); // if(lst+1<=num[pos])ans+=dfs(pos-1,(lst+1==num[pos]),0,lst+1); // if(lst-1>=0)ans+=dfs(pos-1,0,(led && lst-1),lst-1); for(int i=0;i<=top;i++){ if(abs(i-lst)<2)continue; ans+=dfs(pos-1,lmt && i==num[pos],(led && !i),(led&&!i)?-2:i);//有前导零可以随意取值 } if(!lmt && !led)f[pos][lst]=ans; return ans; } int sol(int x){ memset(f,-1,sizeof(f)); len=0; while(x){ num[++len]=x%10; x/=10; } int ans=0; return dfs(len,1,1,-2); } int main(){ scanf("%d%d",&a,&b); printf("%d",sol(b)-sol(a-1)); }