Description
windy定义了一种windy数。
不含前导零且相邻两个数字之差至少为的正整数被称为windy数。
windy想知道，在，总共有多少个windy数？
Input
包含两个整数，。
满足.
Sample Input
1 10
Sample Output
9
比较简单的数位DP，记录前一位的数，但有一个问题，由于不含前导0，如果首位
不确定的话会导致计数错误，，比如012就计算不进去了，因为abs(0-1)<2,所以我们要
设一个变量first来确定首位确定。
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<iostream>#include<queue>#include<cmath>#include<map>#include<stack>#include<bitset>using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )typedef long long LL;typedef pair<int,int>pil;const int INF = 0x3f3f3f3f;LL l,r;int num[50];LL dp[20][10][2];LL dfs(int pos,int pre,int first,int flag){if(pos==0)return first!=0;if(!flag&&dp[pos][pre][first]!=-1)return dp[pos][pre][first];LL res=0;int ed=flag?num[pos]:9;for(int i=0;i<=ed;i++){int f=first;if(first&&abs(pre-i)<2) continue;if(i&&!first)f=1;res+=dfs(pos-1,i,f,flag&&i==ed);}if(!flag) dp[pos][pre][first]=res;return res;}LL solve(LL x){int pos=0;while(x){num[++pos]=x%10;x/=10;}return dfs(pos,-1,0,1);}int main(){CLEAR(dp,-1);while(~scanf("%lld%lld",&l,&r)){LL ans=solve(r)-solve(l-1);printf("%lld\n",ans);}return 0;}
人格的完善是本，财富的确立是末。
