BZOJ 1026：windy数（数位DP）

http://www.lydsy.com/JudgeOnline/problem.php?id=1026

1026: [SCOI2009]windy数

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 5561 Solved: 2493
[Submit][Status][Discuss]

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 。

题意比较简单，这里有点蛋疼的是第一个样例我一开始看不懂，然后问了别人才知道例如第一个样例 1 10 的答案是 1 - 9。
所以可能最高位如果前面都是零的话，那么它可以任意选择一个数（0 - 位上限）
如果最高位前面不全都是零的话,那么它就要按照规则即和前一位相差2来取。
还是太弱了。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 #define N 35

 //long long dp[N][15][2][2];

 long long dp[N][][];

 int bit[N];

 /*

 zero判断前面是不是全都是 0,

 1的话说明前面没有前导零,有值

 0的话说明前面没有值,都是零

 */

 //我一开始的写法

 //long long dfs(int pos, int pre, int  st, int zero, int flag)

 //{

 //    if( !pos ) return st;

 //    if( zero && !flag && dp[pos][pre][st][zero] != -1 ) return dp[pos][pre][st][zero];

 //

 //    long long ans = 0;

 //    int u = flag ? bit[pos] : 9;

 //

 //    if( zero == 0 ){

 //        for(int i = 0; i <= u; i++){

 //            ans += dfs(pos - 1, i, i == 0 ? 0 : 1, i == 0 ? 0 : 1, flag && i==u);

 //        }

 //    }

 //    else{

 //        for(int i = 0; i <= u; i++){

 //            if( abs(pre - i) >= 2 ){

 //                ans += dfs(pos - 1, i, 1, 1, flag && i==u);

 //            }

 //        }

 //    }

 //

 //    if( zero && !flag ) dp[pos][pre][st][zero] = ans;

 //    return ans;

 //}

 //看了别人的写法,简化了很多

 long long dfs(int pos, int pre, int zero, int flag)

 {

     if( !pos ) return ;

     if( zero && !flag && ~dp[pos][pre][zero] ) return dp[pos][pre][zero];

     long long ans = ;

     int u = flag ? bit[pos] : ;

     for(int i = ; i <= u; i++){

         if( !zero || abs(pre - i) >=  )

 /*

 例如第一个样例 1 10 的答案是 1 - 9

 所以可能最高位如果前面都是零的话，那么它可以任意选择一个数（0 - u）

 如果最高位前面不行全都是零的话,那么它就要按照规则即和前一位相差2来取

 这一题的没有前导零还有第一个样例搞得我很迷糊。我还是太弱了

 */

             ans += dfs(pos - , i, i || zero, flag && i==u);

     }

     if( !flag ) dp[pos][pre][zero] = ans;

     return ans;

 }

 long long solve(long long x)

 {

     int l = ;

     while(x>){

         bit[++l] = x % ;

         x /= ;

     }

 //    return dfs(l, 0, 0, 0, 1);

     return dfs(l, , , );

 }

 int main()

 {

     long long a, b;

     cin >> a >> b;

     memset(dp, -, sizeof(dp));

     if(a > b) swap(a, b);

 //    cout << solve(b) <<  "  " << solve(a-1) << endl;

     cout << solve(b) - solve(a-) << endl;

     return ;

 }

巴特西