BZOJ 1026 Windy数
题意：
给你两个数l，r，求[l，r]中不含前导零且相邻两个数字之差至少为2的正整数个数。
题解：
首先很容易想到dfs(x,pre,lim)，pre表示的是前一位的数字。但是如果这样就会有一个问题，举个例子，如果r=1000，对于数字15，它本身是符合要求的，但在dp中，它被看作了0015，这样的话前2位的差为0，就被当作不符合要求的数排除掉了。为了解决这个问题，我们在dp是再加入一个状态led，表示比当前位高的几位是不是全都是前导0，而在转移时，如果led为1，就不用排除差小于2的情况了。
接下来给出代码：
#include<cstdio> #include<cstring> int f[15][10],a[15],cnt; int abs(int x){return x<0?-x:x;} int dfs(int x,int pre,bool led,bool lim){ if(x==0) return 1; if(!led&&!lim&&f[x][pre]!=-1) return f[x][pre]; int ans=0,maxl=lim?a[x]:9; for(int i=0;i<=maxl;++i) if(led||(!led&&abs(i-pre)>=2)) ans+=dfs(x-1,i,led&&!i,lim&&i==maxl); if(!led&&!lim) f[x][pre]=ans; return ans; } int solve(int x){ for(cnt=0;x;x/=10) a[++cnt]=x%10; return dfs(cnt,0,1,1); } int main(){ memset(f,-1,sizeof f); int a,b; scanf("%d%d",&a,&b); printf("%d",solve(b)-solve(a-1)); return 0; }