Oak_limy 的 博客

数位dp是什么

字面意思
数位dp往往都是一样的题型，给定一个闭区间 $[l,r]$，让你求这个区间中满足某种条件的数的总数
感觉很有套路

例题

P2657 [SCOI2009] windy 数
做法：
这大概是数位dp模板题或者入门题，这种题还是挺套路的
我们设dp[i][j]为长度i中最高位是j的windy数的个数
dp[i][j]=$\sum\limits_{k=0}^{9}[abs(j-k)>=2]$
每一步的转移都是前一位的和转移过来的
先初始化所有的dp[i][j]
接着算$[a,b]$区间的所有windy数

#define MAXN 20
int a[MAXN],dp[MAXN][MAXN],n,m;
void init(){ //初始化
	for(int i=0;i<=9;i++)dp[1][i]=1; //要注意0,1,2,3,4...9都属于windy数 
	for(int i=2;i<=10;i++){   //枚举从第二位开始的每一位
		for(int j=0;j<=9;j++){     //第i位上的数
			for(int k=0;k<=9;k++){ //从上一位的数转移过来
				if(fabs(j-k)>=2)dp[i][j]+=dp[i-1][k]; //状态转移
			}
		}
	}
}
int work(int x){  //开始计算
	int len=0;
	ll ans=0;
	memset(a,0,sizeof(a));
	while(x>0){
		a[++len]=x%10;
		x/=10;
	} //算位数，用a数组存每一位，要注意这样存的是倒着存的，len位是最高位
	// 1. 位数小于len，则无需考虑与x的大小关系
	for(int i=1;i<len;i++){  //1~len-1位
		for(int j=1;j<=9;j++){ //最高位只能取1~9
			ans+=dp[i][j];
		}
	}
	// 2.len位，最高位小于原数最高位，也不用考虑与x的大小关系
	for(int i=1;i<a[len];i++){
		ans+=dp[len][i];
	}
	// 3. len位，最高位等于原数最高位，较为复杂，需要考虑与x的大小关系
	for(int i=len-1;i>=1;i--){ //处理 1~len-1位
		for(int j=0;j<=a[i]-1;j++){ //第i位为j
			if(abs(j-a[i+1])>=2)ans+=dp[i][j]; //计算
		}
		if(abs(a[i+1]-a[i])<2)break; //小于2直接跳过
	}
	return ans;
}
int main(){
	cin>>n>>m;
	init();
	cout<<work(m+1)-work(n)<<endl;
    /*这里有的人会说为什么不是work(m)-work(n-1)
       那是因为每次算work如果自己是windy数，但不会带上自己
       所以需要计算work(x+1)，work(m+1)-work(n-1+1)，小细节需要注意一下
       如果写work(m)-work(n-1)只能得90分
                                                                          */
	return 0;
}