【bzoj1026】[SCOI2009]windy数数位dp

题目描述

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 <cstdio>

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;

}

巴特西

【bzoj1026】[SCOI2009]windy数数位dp

最新文章

热门文章

巴特西

【bzoj1026】[SCOI2009]windy数 数位dp

最新文章

热门文章

【bzoj1026】[SCOI2009]windy数数位dp