[SCOI2009] [BZOJ1026] windy数

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

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll A,B;

int k[20],pos;//存数字各位

ll dp[20][10];//第i位为j的数字个数(不能大小限制)

/*

pos : 当前考虑的第pos位，例如十进制数12345,5为第0位

pre : 当前位的前一位的数字

lead ： 是否有前导0，比如之前枚举的两位 00xxx，在枚举3位时是有前导0的。

limit : 是否有大小限制，比如枚举了12xxx,在枚举3位时最大枚举到3

*/

ll dfs(int pos,int pre,bool lead,bool limit){

    if(pos == -1) return 1;

    if(!limit && !lead && dp[pos][pre])return dp[pos][pre];

    int up = limit ? k[pos] : 9;//确定枚举上界

    ll res = 0;

    for(int i=0;i<=up;i++){

        if(lead){

            if(i == 0){

                res += dfs(pos-1,0,true,false);

            }

            else{

                res += dfs(pos-1,i,false,limit && i == k[pos]);

            }

        }else{

            if(abs(i-pre) < 2)continue;

            res += dfs(pos-1,i,false,limit && i == k[pos]);

        }

    }

    if(!limit && !lead)dp[pos][pre] = res;

    return res;

}

ll solve(ll x){

    int pos = 0;

    while(x){

        k[pos++] = x % 10;

        x /= 10;

    }

    return dfs(pos-1,0,true,true);

}

int main(){

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

    printf("%lld\n",solve(B) - solve(A-1));

    return 0;

}

巴特西

[SCOI2009] [BZOJ1026] windy数

最新文章

热门文章