BZOJ1026_windy数

链接：BZOJ1026

题意：【A，B】区间内，有多少个所有相邻数位数值之差不小于2的数

还是来想记忆化的数位DP

首先len肯定是一维变量，flag是一维，既然相邻数位数值有关系，那么上一位数值必须要记录，设为before

如果就dp【len】【before】行吗？

可以，但是dfs记忆化的时候，就三维变量是不行的

因为要判断最高位和前导0

当最高位枚举的时候，可以是0，从前到后一直是0也可以，但是这个数是0，并且只能算作一次

所以呢，记忆化的时候，需要一个bool变量，zero

zero为1，说明之前枚举的高位已经有值了

zero为0，说明之前枚举的高位一直是0，如果一直是0，也不能在记忆化的时候直接返回，跟flag的道理是一样的

其他细节见代码

long long m,n,dp[20][10];
int digit[20];

long long dfs(int pos,int before,bool zero,bool flag){
	if (pos==0) return 1;
	if (flag&&dp[pos][before]!=-1&&zero) return dp[pos][before];
	long long ans=0;
	int num=flag?9:digit[pos];
	for(int i=0;i<=num;i++)
		if (!zero||abs(before-i)>=2)
			ans+=dfs(pos-1,i,zero||i>0,flag||i<num);
	if (flag&&zero) dp[pos][before]=ans;
	return ans;
}

long long calc(long long x){
	int len=0;
	while(x){
		digit[++len]=x%10;
		x/=10;
	}
	return dfs(len,11,0,0);
}

int main(){
	//input;
	memset(dp,-1,sizeof(dp));
	while(scanf("%lld%lld",&m,&n)!=EOF)
		printf("%lld\n",calc(n)-calc(m-1));
	return 0;
}