Time:2016.08.14 Author:xiaoyimi 转载注明出处谢谢
思路： 依旧蛋疼的数位DP f[i][j]表示有i位，且最高位为j的windy数个数 转移方程比较好写 关键是具体求值的时候不太好弄 从小位往高位求 cal(i)实际上算出的是1~i-1的windy数 所以判断一下i是否为windy数就可以了 代码：
#include<cstdio> using namespace std; int a,b; int f[11][10],num[11]; int ab(int x){return x>=0?x:-x;} bool check(int x) { if (!x) return 0; int last=x%10; x/=10; for (;x;last=x%10,x/=10) if (ab(x%10-last)<2) return 0; return 1; } int cal(int x) { num[0]=0; int last,ans=0,k=x; num[++num[0]]=k%10;k/=10; for (;k;k/=10) num[++num[0]]=k%10; for (int i=1;i<num[0];i++) for (int j=1;j<=9;j++) ans+=f[i][j]; for (int i=1;i<num[num[0]];i++) ans+=f[num[0]][i]; last=num[num[0]]; for (int i=num[0]-1;i;last=num[i],i--) { for (int j=0;j<num[i];j++) if (ab(last-j)>=2) ans+=f[i][j]; if (ab(last-num[i])<2) break; } return ans+check(x); } main() { for (int i=0;i<=9;i++) f[1][i]=1; for (int i=2;i<=10;i++) for (int j=0;j<=9;j++) for (int k=0;k<=9;k++) if (ab(j-k)>=2) f[i][j]+=f[i-1][k]; scanf("%d%d",&a,&b); printf("%d",cal(b)-cal(a-1)); }