luogu2657|SCOI2009|windy数

$windy$定义了一种$windy$数。不含前导零且相邻两个数字之差至少为$2$的正整数被称为$windy$数。 $windy$想知道,

在$[A,B]$,总共有多少个$windy$数?

数位$DP$裸题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#define L 30
int a[L],f[L][L][2];
int dp(int x)
{
int l=0,r=0;
if(x==0)return 0;
while(x)
{
a[++l]=x%10;
x/=10;
}//得到x的长度和每一位
fr(i,1,l)
fr(j,0,9)
fr(k,0,1)
f[i][j][k]=0;//init
fr(i,1,a[l])
f[l][i][i==a[l]]=1;//最高位
fd(i,l-1,1)
{
fr(j,1,9)
f[i][j][0]=1;//处理只有i位的情况
fr(j,0,a[i])
if(abs(j-a[i+1])>=2)f[i][j][j==a[i]]+=f[i+1][a[i+1]][1];//转移上一位贴着x的(下面有解释)
fr(j,0,9)
fr(k,0,9)
if(abs(j-k)>=2)
f[i][j][0]+=f[i+1][k][0];//转移上一位没贴着x的
}
fr(i,0,9)
fr(j,0,1)
r+=f[1][i][j];
return r;
}
int main()
{
int l=read()-1,r=read();
printf("%d\n",dp(r)-dp(l));
return 0;
}

贴着$x$的:

若$x=233333$,处理后就是$x=\{2,3,3,3,3,3\}$

当前处理到了第$i$位

设$i=3$

若$y=\{2,3\}$,那么称$y$贴着$x$

因为$y$下一位取值只有$[0,3]$(不考虑$windy$数性质)

若$y$下一位取$3$那么$y$依然是贴着$x$的

反之,若$y=\{2,2\}$,那么$y$下一位取值$[0,9]$

则$y$不是贴着$x$的