题目大意：求在[l,r]中不含前导零且相邻两个数字之差至少为2的正整数的个数
数位DP f[pos][digit][is_maxx][is_zero]代表在pos位上填上digit这个数。is_maxx是前pos位是否顶格，is_zero是前pos位是否都为0. 感谢todobe神犇教我写数位DP的正确姿势 我的代码写的这么有道理自己慢慢看吧
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; int DP(int x) { if(!x) return 0; char s[50]; sprintf(s+1,"%d",x); int len=strlen(s+1); static int f[15][15][2][2]; memset(f,0,sizeof f); f[0][0][1][1]=1; for(int pos=1;pos<=len;pos++) for(int now_digit=0;now_digit<10;now_digit++) for(int last_is_maxx=0;last_is_maxx<2;last_is_maxx++) { if(last_is_maxx && now_digit>s[pos]-'0') continue; int now_is_maxx=0; if(last_is_maxx && now_digit==s[pos]-'0') now_is_maxx=1; for(int last_is_zero=0;last_is_zero<2;last_is_zero++) for(int last_digit=0;last_digit<10;last_digit++) { if(last_is_zero && last_digit!=0) break; int now_is_zero=0; if(last_is_zero && now_digit==0) now_is_zero=1; if(abs(now_digit-last_digit)>1 || last_is_zero) f[pos][now_digit][now_is_maxx][now_is_zero]+=f[pos-1][last_digit][last_is_maxx][last_is_zero]; } } int ans=0; for(int i=0;i<10;i++) ans+=f[len][i][0][0]+f[len][i][1][0]; return ans; } int main() { int l,r; scanf("%d%d",&l,&r); printf("%d\n",DP(r)-DP(l-1)); return 0; }