bzoj1026--SCOL2009--windy数(数位dp练习1)

本文主要是介绍bzoj1026--SCOL2009--windy数(数位dp练习1)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

windy数

Time Limit:1000MS Memory Limit:165888KB 64bit IO Format:%lld & %llu

Submit Status

Description

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

Input

包含两个整数，A B。

Output

一个整数。

Sample Input

【输入样例一】
1 10【输入样例二】
25 50

Sample Output

【输出样例一】
9【输出样例二】
20【数据规模和约定】
20%的数据，满足 1 <= A <= B <= 1000000 。
100%的数据，满足 1 <= A <= B <= 2000000000 。

求在n和m之间相邻的差要大于等于2的个数

dp[i][j]代表i位，且以j开头的数的个数。其中符合相邻的差要大于等于2 ；

计算n到m之间的个数 = 用1到m的个数 - 1到n的个数。

从高位开始，累加计数。当高位中已经不满足条件后直接退出。

忽略前导0，所以累加是前导为0的另外累加。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std ;
#define LL long long
LL dp[12][10] ;
LL digit[12] , cnt ;
void init()
{memset(dp,0,sizeof(dp)) ;int i , j , k ;for(i = 0 ; i <= 9 ; i++)dp[1][i] = 1 ;for(i = 2 ; i <= 10  ;i++)for(j = 0 ; j < 10 ; j++)for(k = 0 ; k < 10 ; k++)if( abs(j-k) >= 2 ){dp[i][j] += dp[i-1][k] ;}
}
LL solve(LL temp)
{LL ans = 0 , i , j ;cnt = 0 ;memset(digit,0,sizeof(digit)) ;while(temp){digit[++cnt] = temp % 10 ;temp /= 10 ;}for(j = 1 ; j < digit[cnt] ; j++)ans += dp[cnt][j] ;for(i = cnt-1 ; i > 0 ; i--)for(j = 1 ; j < 10 ; j++)ans += dp[i][j] ;for(i = cnt-1 ; i > 0 ; i--){for(j = 0 ; j < digit[i] ; j++)if( abs(digit[i+1]-j ) >= 2 )ans += dp[i][j] ;if( abs(digit[i+1]-digit[i]) < 2 )break ;}return ans ;
}
int main()
{init() ;LL a , b ;while( scanf("%lld %lld", &a, &b) != EOF ){printf("%lld\n", solve(b+1)-solve(a) );}return 0;
}

这篇关于bzoj1026--SCOL2009--windy数(数位dp练习1)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！