题目大意：求[a,b]区间内有多少个数满足任意相邻两个位置上的数>=2
首先将[a,b]分解为[1,b]-[1,a-1]
然后令f[i][j]为以i开头的j位windy数有多少个
然后十进制拆分即可
此题有些要讨论的地方：
1.小心爆int
2.最后一位要单独讨论
3.已经确定的数字是否不满足windy数的条件
4.一开始的[0,99...99]的区间需要单独计算
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int f[10][20];//f[i][j]表示以i开头的j位windy数有多少
bool Conflict(int x)
{
int temp=-10;
while(x)
{
if(abs(temp-x%10)<2)
return true;
temp=x%10;x/=10;
}
return false;
}
int Digital_DP(ll x)
{
int i,j,re=0;
ll pos,now;
for(i=1,pos=10;pos<=x;i++,pos*=10)
{
for(j=1;j<=9;j++)
re+=f[j][i];
}
now=pos/=10;--i;
while(now<x)
{
while(now+pos<=x)
{
int temp=now/pos%10;
if( !Conflict(now/pos) )
for(j=0;j<=9;j++)
if(abs(j-temp)>=2||pos==1)
re+=f[j][i];
now+=pos;
}
if( Conflict(now/pos) )
break;
pos/=10;--i;
}
return re;
}
int main()
{
int i,j,k;
f[0][0]=1;
for(i=0;i<=9;i++)
f[i][1]=1;
for(j=2;j<=10;j++)
for(i=0;i<=9;i++)
for(k=0;k<=9;k++)
if(abs(i-k)>=2)
f[i][j]+=f[k][j-1];
int a,b;
cin>>a>>b;
cout<<Digital_DP(b+1)-Digital_DP(a)<<endl;
}