BZOJ 1026 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 。

数位dp裸题：f[i][j][k]表示考虑至第i位，填j,且属于k状态的方案数。k = 0为危险状态，k = 1为安全状态。

设A的位数为p1，B的为p2。先dp位数为p1的满足条件数有几个，再dp位数<p1且满足条件的数有几个(全是安全态)。两者相加即为<=A的满足条件的数有几个了。

ans = ans(B) - ans(A-1);

具体见代码(可能略丑，仅供参考):

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<cstdlib>

 using namespace std;

 #define maxn 15

 int A,B,sum,f[maxn][][];

 int num[maxn];

 inline int len(int lim)

 {

     int ret = ,pos = ,t = lim;

     while (lim) { ++ret; lim/=; }

     memset(num,,sizeof(num));

     while (t) { ++pos; num[ret - pos + ] = t%; t /= ; }

     return ret;

 }

 inline int dp(int lim)

 {

     if (lim == ) return ;

     int ret = ,n = len(lim),i,j,k;

     memset(f,,sizeof(f));

     for (i = ;i < num[];++i) f[][i][] = ;

     f[][num[]][] = ;

     for (i = ;i < n;++i)

         for (j = ;j < ;++j)

         {

             if (f[i][j][])

                 for (k = ;k < ;++k)

                 {

                     if (abs(k-j) < ) continue;

                     f[i+][k][] += f[i][j][];

                 }

             if (!f[i][j][]) continue;

             for (k = ;k <= num[i+];++k)

             {

                 if (abs(k-j) < ) continue;

                 if (k == num[i+])

                     f[i+][k][] += f[i][j][];

                 else f[i+][k][] += f[i][j][];

             }

         }

     for (i = ;i < ;++i) for (j = ;j < ;++j) ret += f[n][i][j];

     memset(f,,sizeof(f));

     for (i = ;i < ;++i) f[][i][] = ;

     for (i = ;i < n-;++i)

         for (j = ;j < ;++j)

         {

             if (!f[i][j][]) continue;

             for (k = ;k < ;++k)

             {

                 if (abs(j - k) < ) continue;

                 f[i+][k][] += f[i][j][];

             }

         }

     for (i = ;i < n;++i) for (j = ;j < ;++j) ret += f[i][j][];

     return ret;

 }

 int main()

 {

     freopen("1026.in","r",stdin);

     freopen("1026.out","w",stdout);

     scanf("%d %d",&A,&B);

     sum = dp(B);

     sum -= dp(A-);

     printf("%d",sum);

     fclose(stdin); fclose(stdout);

     return ;

 }

巴特西