BZOJ 1026 [SCOI2009]windy数

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

HINT

【数据规模和约定】 100%的数据，满足 1 <= A <= B <= 2000000000 。

Source

数位dp。 预处理，设dp[i][j]表示i位数，最高位是j的方案数，状态转移比较简单。 询问，拆为前缀和，分为三种情况： 1共有i位数，最高位小于原数最高位。 2共有1...len-1位数，最高位任意。 3最高位分别与原数对应，具体见代码。 #include<iostream> #include<cstring> #include<cstdio> using namespace std; long long l,r,dp[33][11]; //i位数，最高位是j的windy数个数 int abso(int x) { return x<0?-x:x; } void init() { for(int i=0;i<=9;i++) dp[1][i]=1; for(int i=2;i<=11;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) if(abso(j-k)>=2) dp[i][j]+=dp[i-1][k]; } long long query(long long x) { int tot=0,num[33]; long long ans=0; memset(num,0,sizeof(num)); while(x) { num[++tot]=x; x/=10; } for(int i=1;i<num[tot];i++) ans+=dp[tot][i]; for(int i=tot-1;i;i--) for(int j=1;j<=9;j++) ans+=dp[i][j]; for(int i=tot-1;i;i--) { for(int j=0;j<num[i];j++) if(abso(num[i+1]-j)>=2) ans+=dp[i][j]; if(abso(num[i]-num[i+1])<2) break; } return ans; } int main() { init(); scanf("%lld%lld",&l,&r); printf("%lld\n",query(r+1)-query(l)); return 0; }