[每日一题]:Windy 数

题目:

考察点:

数位 DP

数位DP 的板子戳这里:

https://www.cnblogs.com/prjruckyone/category/1754376.html

侃侃:

这道题与模板只有一点点稍微的不同,还需要判段一下 前导 0 
因为我们是从高位开始枚举的,枚举到最后可能会出现这样的情况
0004,显然这个数不是 Windy 数,但是我们可以看到 0 和 4 相差
是 >= 2 的，所以如果不判断前导 0 的话就会出现多加的情况，其他
的和模板类似。

Code:

#include <cstdio>
#include <string>
#include <cmath> 
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 25;

typedef long long LL;

LL dp[maxn][maxn],a[maxn];

LL l,r;

LL DFS(int pos,int st,bool limit,bool lead) {
	if(pos == -1) return 1;
	// 如果上一位不是最高位并且上一位不是前导 0  
	if(!limit && !lead && dp[pos][st] != -1) return dp[pos][st];
	LL res = 0;
	int up = limit?a[pos]:9;
	for(int i = 0; i <= up; i ++) {
		
		if(abs(i - st) < 2 && !lead) {
			continue;
		}
		res += DFS(pos - 1,i,limit && (i == a[pos]),lead && i == 0);
	}
	if(!limit && !lead) dp[pos][st] = res;
	return res;
}

LL solve(LL x) {
	int len = 0;
	while(x) {
		a[len ++] = x % 10;
		x /= 10; 
	}
	// 刚开始肯定是没有前导 0 的,并且是最高位 
	return DFS(len - 1,0,1,1);
}

int main(void) {
	memset(dp,-1,sizeof(dp));
	scanf("%lld%lld",&l,&r);
	printf("%lld
",solve(r) - solve(l - 1));
	return 0;
} 

后记:

DP 博大精深,目前了解的只是皮毛,DP 确实不好搞啊啊啊！