[SCOI2009]windy数

Description

BZOJ1026
Luogu2657
求相邻两数位之间的差至少为2的数字个数。

Solution

数位DP

Code

#include <cstdio>
#include <cstring>

const int N = 20;

int dp[N][N], a[N];

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

int dfs(int pos, int last, bool lead, bool limit) {
	if (pos == -1) return 1;
	if (!lead && !limit && dp[pos][last] != -1) return dp[pos][last];
	int up = limit ? a[pos] : 9;
	int ans = 0;
	for (int i = 0; i <= up; ++i) {
		if (lead || abs(i-last) >= 2) {
			ans += dfs(pos-1, i, lead && i==0, limit && i == a[pos]);
		}
	}
	if (!limit && !lead) dp[pos][last] = ans;
	return ans;
}

void init() {
	memset(dp, -1, sizeof dp);
}

int calc(int x) {
	int pos = -1;
	while (x) a[++pos] = x % 10, x /= 10;
	int ans = dfs(pos, 0, true, true);
	return ans;
}

int main() {
	init();
	int l, r;
	scanf("%d%d", &l, &r);
	printf("%d
", calc(r) - calc(l-1));
	return 0;
}