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

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;
}

------ 本文结束 ------