P2188 小Z的 k 紧凑数题解（数位DP）

题目链接

解题思路

数位DP，把每一个数位的每一个数对应的可能性表示出来，然后求\(num(1,r)-num(1,l-1)\)，其中\(num(i,j)\)表示\([i,j]\)区间里符合要求的数的个数。

其中，\(dp[i][j]\)表示第\(i\)位数字为\(j\)的选择种数。

计算的时候，比如\(num(456)\)，就拆开为\(num(1,99)+num(100,399)+num(400,449)+num(450,455)+num(456,456)\)

AC代码

#include<stdio.h>

long long k,dp[20][14],l,r;

int absf(int a){

	if(a<0)return -a;

	return a;

}

void dpf(){

	int i,j,m;

	for(i=0;i<=9;i++)dp[0][i]=1;//个位数，初始化为1

	for(i=1;i<20;i++)//这是总共的位数

		for(j=0;j<=9;j++)//这是这一位

			for(m=0;m<=9;m++)//这是上一位

				if(absf(j-m)<=k)dp[i][j]+=dp[i-1][m];//这一位和上一位满足条件则加上

}

long long num(long long x){

	int n[20]={0},cnt=0,i,j;

	long long ans=0;

	while(x>0){

		n[cnt++]=x%10;

		x/=10;

	}

	//首位为0

	for(i=0;i<cnt-1;i++)

		for(j=1;j<=9;j++)

			ans+=dp[i][j];

	//首位为[1,n[cnt-1])

	if(cnt>0)for(i=1;i<n[cnt-1];i++)ans+=dp[cnt-1][i];

	//首位为n[cnt-1]

	for(i=cnt-2;i>=0;i--){

		for(j=0;j<n[i];j++){

			if(absf(n[i+1]-j)<=k)ans+=dp[i][j];

		}

		if(absf(n[i+1]-n[i])>k)break;

		//非常重要！！前几位已经不满足绝对值之差不大于k之后就不能再继续下去了

		if(!i&&absf(n[i+1]-j)<=k)ans+=dp[i][j];//这里相当于计算那个num(456,456)

	}

	if(cnt==1)ans++;//这里也相当于计算那个num(456,456)，但是个位数不会进入上面那个循环

	return ans;

}

int main(){

	scanf("%lld%lld%lld",&l,&r,&k);

	dpf();

	printf("%lld",num(r)-num(l-1));

	return 0;

}

巴特西

P2188 小Z的 k 紧凑数题解（数位DP）

题目链接

解题思路

AC代码

最新文章

热门文章

巴特西

P2188 小Z的 k 紧凑数 题解（数位DP）

题目链接

解题思路

AC代码

最新文章

热门文章

P2188 小Z的 k 紧凑数题解（数位DP）