「Bzoj 1026」「SCOI2009」windy数 (数位DP(模板))

发表于 | 分类于 | | + s

Bzoj 1026
题意：不含前导零且相邻两个数字之差至少为$2$的正整数被称为windy数。 在$A$和$B$之间，包括$A$和$B$，总共有多少个windy数？
数位DP模板。设$dp(i, pre)$为第$i$位前面的值为$pre$的windy数的个数。
然后一般数位DP用记忆化完成。所以记忆化。基本思想是试填法。
具体实现看代码，其中的限制意思是本位上不能填完所有的数，例如最大数字为41002，如果首位填了4，后面第二位只能填0、1，若后面第二位填了1，则后面第三位只能填0。如果第二位填了0，则后面第三位可以填$[0,9]$中任意数字。以此类推。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky { 

    int A, B, len, b[20], dp[20][20];

    int abss(int x) {return x > 0 ? x : -x;}

    int dfs(int a, int pre, int limit) {
        if (a == 0) return 1; // 合法情况
        if (pre != -233 && !limit && dp[a][pre] >= 0) return dp[a][pre];
        //当前不是前导零且没有被限制且已经记忆化搜索过
        int ret = 0;
        int ed = (limit ? b[a] : 9); // 上限
        for (int i = 0; i <= ed; ++i) {
            if (abss(i - pre) >= 2) {
                int p = i;
                if (pre == -233 && i == 0) p = -233; // 前导零
                ret += dfs(a - 1, p, (limit && (i == ed)));
            }
        }
        if (pre != -233 && !limit) dp[a][pre] = ret;
        //不是前导零并且没有限制才记忆化
        return ret;
    }
    int getans(int x) {
        int tmp = x; len = 0;
        while (tmp) b[++len] = tmp % 10, tmp /= 10; // 分解数位
        ms(dp, -1);
        return dfs(len, -233, 1);
    }

    void clean() {
    }
    int solve() {
        clean();
        scanf("%d%d", &A, &B);
        printf("%d\n", getans(B) - getans(A - 1)); // 分问题
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------