吐槽一句：bzoj 卡~到~爆~了！！！！！
题目：
题解：
f[i][j]表示i位数最后一位是j
细节就是处理前导0
代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
//f[i][j]表示i位数最后一位是j
int f[20][20],digi[20];
void dp()
{
int i,j,k;
for (i=0;i<=9;i++)
f[1][i]=1;
for (i=2;i<=10;i++)
for (j=0;j<=9;j++)
for (k=0;k<=9;k++)
if (abs(j-k)>=2)
f[i][j]+=f[i-1][k];
}
int find(int n)
{
int cnt=0,ans=0,i,j;
memset(digi,0,sizeof(digi));
while (n) digi[++cnt]=n%10,n/=10;
for (i=1;i<cnt;i++)//个位数
for (j=1;j<=9;j++)
ans+=f[i][j];
for (i=cnt;i>=1;i--)
{
for (j=0;j<digi[i];j++)
if (i==cnt&&!j) continue; //前导0
else if (abs(j-digi[i+1])>=2 || i==cnt) // 前面没有数
ans+=f[i][j];
if (i!=cnt && abs(digi[i+1]-digi[i])<2) break;
}
return ans;
}
int main()
{
int a,b;
dp();
scanf("%d%d",&a,&b);
printf("%d",find(b+1)-find(a));
}