[数据结构与算法]1589 不要 62(LOJ10167) 数据弱暴力100分 数位DP 局部的记忆化搜索

总目录

在线测评地址(ybt)

在线测评地址(LOJ)

1.暴力方式

枚举，分析出每位上数据，统计4，统计62情况，总数扣除不符合的数据，就是有效数据。

ybt

通过

LOJ

?暴力代码如下：

#include <bits/stdc++.h>
using namespace std;
int judge(int x){//返回0表示无效数据 
	int lt,rt;
	rt=x%10;
	x/=10;
	if(rt==4)return 0;//4
	while(x){//低位向高位扫描 
		lt=x%10;
		if(lt==4)return 0;//4
		if(lt==6&&rt==2)return 0;//62
		rt=lt;
		x/=10;
	}
	return 1;
}
int main(){
	int n,m,cnt,x;
	while(1){
		scanf("%d%d",&n,&m);
		if(n==0&&m==0)break;
		cnt=0;
		for(x=n;x<=m;x++)
			if(judge(x)==0)
				cnt++;
		printf("%d\n",m-n+1-cnt);
	}
	return 0;
}

2.数位DP

以下内容，可以结合后续的AC代码进行阅读。

dp[pos][pre]代表的是什么意思?

pos表示当前遍历的是第几位，pre表示前一位是几
??? ?
dp[pos][pre]就是记录了遍历第pos位时，前一位为pre时的状态数
??? ?
举例子
假设数5762，那么数位有4位
数位数组是这样存储的2 6 7 5
数组从0位开始，
所以是 0位 到 3位
那么当pos为2的时候，前一位(即第3位)有0 - 5这些情况
那么dp[2][0-5]分别存储了dp[2][0],dp[2][1]。。。。等等 这些情况

记搜过程

从起点向下搜索，到最底层得到方案数，一层一层向上返回答案并累加，最后从搜索起点得到最终答案。

对于[l,r]区间问题，我们一般把他转化为两次数位dp,即找[0,r]和[0,l?1]两段，再将结果相减就得到了我们需要的[l,r]

状态设计

如果理解了上述过程，我们需要考虑的就是怎样判断现在在哪一层，怎样判断当前的状态——这就需要我们传进一些参量。

dfs函数需要哪些参量？

1. 首先是数位dp基本的量数字位数pos，最高位限制limit

2. 由于数位dp解决的大多是数字组成问题，所以经常要比较当前位和前一位或前几位的关系（根据题意而定），所以一般在dfs()中也要记录前一位或前几位数pre方便比较。

3. 除此之外还可以传进更多参量以区分状态，视题意而定。

最高位标记limit

我们知道在搜索的数位搜索范围可能发生变化；

举个例子：我们在搜索[0,567]的数时，显然最高位搜索范围是0~5，而后面的位数的取值范围会根据上一位发生变化：

1. 当最高位是1~4时，第二位取值为[0,9];
2. 当最高位是5时，第二位取值为[0,6]（再往上取就超出右端点范围了）

为了分清这两种情况，我们引入了limit标记：

1. 若当前位limit=1而且已经取到了能取到的最高位时，下一位limit=1；
2. 若当前位limit=1但是没有取到能取到的最高位时，下一位limit=0；
3. 若当前位limit=0时，下一位limit=0。

我们设这一位的标记为limit，这一位能取到的最大值为res，则下一位的标记就是i==res&&limit（i枚举这一位填的数）

dp值的记录和使用

最后我们考虑dp数组下标记录的值

本文介绍数位dp是在记忆化搜索的框架下进行的，每当找到一种情况我们就可以这种情况记录下来，等到搜到后面遇到相同的情况时直接使用当前记录的值。

dp数组的下标表示的是一种状态，只要当前的状态和之前搜过的某个状态完全一样，我们就可以直接返回原来已经记录下来的dp值。

再举个例子

假如我们找[0,123456]中符合某些条件的数

假如当我们搜到1000??时，dfs从下返上来的数值就是当前位是第1位，前一位是0时的方案种数，搜完这位会向上，这是我们可以记录一下：当前位第1位，前一位是0时，有这么多种方案种数

当我们继续搜到1010??时，我们发现当前状态又是搜到了第1位，并且上一位也是0，这与我们之前记录的情况相同，这样我们就可以不继续向下搜，直接把上次的dp值返回就行了。

注意，我们返回的dp值必须和当前处于完全一样的状态，这就是为什么dp数组下标要记录pos,pre等参量了。

最重要的来了————————————————————

接着上面的例子，范围[0,123456]

如果我们搜到了1234??，我们能不能直接返回之前记录的：当前第1位，前一位是4时的dp值？

答案是否定的

我们发现，这个状态的dp值被记录时，当前位也就是第1位的取值是[0,9]，而这次当前位的取值是[0,5]，方案数一定比之前记录的dp值要小。

当前位的取值范围为什么会和原来不一样呢？

如果你联想到了之前所讲的知识，你会发现：现在的limit=1，最高位有取值的限制。

因此我们可以得到一个结论：当limit=1时，不能记录和取用dp值！

没有限制的情况占多数，所以只记录没有高位限制的情况
if(!limit)
{
??? dp[pos][pre] = ans;
}

有limit=1限制的怎dp[pos][pre]么办呢？每次都重新算。

ybt

通过

LOJ

?数位DP代码如下：

#include <bits/stdc++.h>
using namespace std;
int a[10],dp[10][10];
int dfs(int pos,int pre,int limit){
	int ans=0,up,i;
	if(pos==-1)return 1;//遍历到pos=-1位,该次遍历有效,返回计数1
	if(dp[pos][pre]!=-1&&!limit)return dp[pos][pre];//当前没有限制, 
	up=limit?a[pos]:9;//当前位数字上限 
	for(i=0;i<=up;i++){
		if(i==4)continue;//跳过4 
		if(pre==6&&i==2)continue;//跳过62 
		ans+=dfs(pos-1,i,limit&&i==a[pos]);
	}
	if(!limit)dp[pos][pre]=ans;
	return ans;
}
int solve(int x){
	int pos=0;
	while(x){//个位存储在第0位,十位存储在第1位,百位存储在第2位,依次类推 
		a[pos++]=x%10;//将x拆开按位存储在a[]中 
		x/=10; 
	}
	return dfs(pos-1,0,1);
}
int main(){
	int lt,rt;
	while(scanf("%d%d",&lt,&rt)&&lt+rt!=0){
		memset(dp,-1,sizeof(dp));
		printf("%d\n",solve(rt)-solve(lt-1));
	}
	return 0;
} 

《新程序员》：云原生和全面数字化实践

50位技术专家共同创作，文字、视频、音频交互阅读