windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道， 在A和B之间，包括A和B，总共有多少个windy数？
包含两个整数，A B。
一个整数
【数据规模和约定】 100%的数据，满足 1 <= A <= B <= 2000000000 。
人生第一道数位DP。
感谢tyb的耐心指导。
f[i][j]表示i位数，以j开头的windy的数量。
首先预处理f[i][j]的值。（详见代码）
然后对于到x的windy数的个数我们分三种情况讨论。len为x的位数
1.位数小于len，直接加上f[i][j]
2.位数等于len，j<x的开头，加上f[len][j]
3.位数等于len，枚举每一位的情况。（详见代码）
#include<cstdio> #include<cstdlib> #include<cstring> int f[20][20]; int abs(int x) { if(x<0) return -x; return x; } void init() { memset(f,0,sizeof(f)); for(int j=0;j<=9;j++) f[1][j]=1; for(int i=2;i<=10;i++) for(int j=0;j<=9;j++) for(int u=0;u<=9;u++) if(abs(j-u)>=2) f[i][j]+=f[i-1][u]; } int slove(int x1) { int b[20],len=0; while(x1!=0) { int y1=x1; len++; b[len]=y1; x1/=10; } int ans=0; b[len+1]=-1; for(int i=1;i<len;i++) for(int j=1;j<=9;j++) ans+=f[i][j]; for(int j=1;j<b[len];j++) ans+=f[len][j]; for(int i=len-1;i>=1;i--) { for(int j=0;j<b[i];j++) { if(abs(j-b[i+1])>=2) ans+=f[i][j]; } if(abs(b[i]-b[i+1])<2) break; } return ans; } int x,y; int main() { scanf("%d%d",&x,&y); init(); printf("%d",slove(y+1)-slove(x)); }