题目描述

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

输入

包含两个整数，A B。

输出

一个整数，表示答案

样例输入

【输入样例一】

1 10

【输入样例二】

25 50

样例输出

【输出样例一】

9

【输出样例二】

20

---

题解

数位dp

快联赛了重写了一下，发现以前写的太傻逼了= =

由于加一个数位的贡献只与最高位有关，因此设 $f[i][j]$ 表示 $i$ 位数，最高位为 $j$ 的数的个数。

那么显然可以得到 $f[i][j]=\sum\limits_{|j-k|\le 2}f[i-1][k]$ 。

预处理出 $f$ 数组后即可进行数位dp。

先把位数不满的算上，然后再从高位到低位把该位不满的加入答案中。

此时需要记录上一个数位是什么，在枚举当前数位时需要满足当前位的条件。并且如果上一个与当前数位产生冲突则不再有满足条件的数，应当跳出循环。

把询问区间转化为 $[1,n)$ 的半开半闭区间更容易处理一些。

代码中为了避免一些细节（比如最高位只能处理到 $2*10^9$ 之类的），开了long long。

#include 
     
      typedef long long ll;ll f[11][10] , b[11];inline int abs(int x){	return x > 0 ? x : -x;}void init(){	int i , j , k;	b[0] = 1 , b[1] = 10;	for(i = 0 ; i < 10 ; i ++ ) f[1][i] = 1;	for(i = 2 ; i < 11 ; i ++ )	{		b[i] = b[i - 1] * 10;		for(j = 0 ; j < 10 ; j ++ )			for(k = 0 ; k < 10 ; k ++ )				if(abs(j - k) >= 2)					f[i][j] += f[i - 1][k];	}}ll calc(ll n){	int i , j , last = -1 , di = 1;	ll ans = 0;	for(i = 1 ; b[i] <= n ; i ++ )		for(j = 1 ; j < 10 ; j ++ )			ans += f[i][j];	for( ; i ; i -- )	{		for(j = di ; j < n / b[i - 1] % 10 ; j ++ )			if(abs(j - last) >= 2)				ans += f[i][j];		if(abs(n / b[i - 1] % 10 - last) < 2) break;		last = n / b[i - 1] % 10 , di = 0;	}	return ans;}int main(){	init();	ll n , m;	scanf("%lld%lld" , &n , &m);	printf("%lld\n" , calc(m + 1) - calc(n));	return 0;}