题解：P13085 [SCOI2009] windy 数（加强版）

显然，这是一道数位 dp。~~这不是废话吗~~。如果不知道什么是数位 dp，请移步至P2602 [ZJOI2010] 数字计数，那里有超详细的讲解。

其实所有的数位 dp 都一个套路，只是改一下要求。只需要注意一下两数之差为绝对值，不要忘记前导零，再稍微注意一下细节，就可愉快的通过本题了。

思路概述：先将原数按位拆解，在从高位到低位挨个枚举，同时进行记忆化保证时间复杂度。

解释一下：last 之所以要初始化为-2，是为了保证首位可以填0。

代码：

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int dp[20][20][2][2],num[20];
int dfs(int pos,int last,bool flag,bool lead){
	/*
	lead表示是否有前导零，flag表示是否受限制 
	*/
	if(pos==0)return 1;//若pos==0，则表示找到一个可行的数 
	if(dp[pos][last][flag][lead]!=-1)return dp[pos][last][flag][lead];//记忆化优化 
	int ans=0,up=9;
	if(flag)up=num[pos];//up为当前数位可取的最大值 
	for(int i=0;i<=up;i++){
		if(abs(i-last)>=2||lead)ans+=dfs(pos-1,i,flag&&(i==up),lead&&(i==0));
	}
	dp[pos][last][flag][lead]=ans;
	return ans;
}
int work(int x){//预处理  
	memset(dp,-1,sizeof(dp));
	int len=0;
	while(x){
		num[++len]=x%10;
		x/=10;
	}
	return dfs(len,-2,1,1);
}
int a,b;
signed main(){
	scanf("%lld%lld",&a,&b);
	printf("%lld",work(b)-work(a-1));//因为 a 这个数也要被判断，所以是 work(a-1) 
	return 0;
}

~最后，不开long long见祖宗。~

题解：P13085 [SCOI2009] windy 数（加强版）

文章操作

相关推荐

评论

题解：P13085 [SCOI2009] windy 数（加强版）