让我们以一道题目来引入,数位dp的思想。
Tasks - AtCoder Beginner Contest 029
ABC round 029 D
题面:
求 1~N 中,数字1有多少个。 N<=1e9
由于,数据很大,我们无法暴力求解。
故,从数位的角度思考。
以N=345举例,其位数为3。
我们从最高位开始枚举。
思考:加怎样的判断条件,可以使得我们枚举的数不超过N?
我们可以将情况分成2种:
1、从高到低枚举的数位每一位都“贴合” N。
如:34 与 345 , 由于前面的数都贴合,所以当我们枚举下一位的时候,我们枚举的选择只能是 0~5. 也就是0~N在这一位的数位
2、从某一位开始不贴合。
如果我们枚举的数,从某一位开始不贴合的话,那么从这一位之后,每一位的枚举范围,将不受限。即可取0~9
我们考虑将一个flag标记传入dfs中,flag的含义是,我们此位的枚举是否受限。
这里定义一个变量top作为该位能枚举到的上限。
若flag=1,说明我们当前是贴合的,那么我们下一位的枚举将受限。即top = N在此位上的位数
若flag=0,则下一位枚举不受限,即top=9;
现在考虑如何将flag传入下一层。
我们枚举可以利用for(int i=0;i<=top;i++)
,此处的i,就是我们这一层所枚举的数。
如果这个i<top
说明下一位的枚举一定是不受限制的。
但如果 i==top
能说下一层一定受限吗?
不妨分类讨论一下:
1、假设到目前为止,一直是贴合的,那么此时i==top
,下一层的枚举必然受限,因为我们的枚举不能超过N本身。
2、假设在此之前就不受限了,那么即时i==top
,下一层的枚举也是不受限制了,因为始终不可能超过N本身,如(345,099)。
结论:
下一层是否受限,与 i==top
以及 是否一直贴合 有关。所以,当 flag&&i==top
为真时,下一层受限,否则下一层不受限。
所以,我们根据上述的推论,可以得到这样的代码:
ll dfs(int pos,int sum,int flag) { ll ans = 0; if(pos==0)return sum; int max_num = flag ? st[pos] : 9; for (int i = 0; i <= max_num; i++) { ans += dfs(pos - 1, sum + (i == 1), flag && i == max_num); } return ans; }
简单解释一下:
ll dfs(int pos,int sum,int flag) // 三个参数是,当前枚举到了第几位(从高到低枚举)、枚举到现在1的数量、是否受限标志
if(pos==0)return sum; // 如果枚举完了,直接返回sum
int max_num = flag ? st[pos] : 9;// 枚举的上限 ans += dfs(pos - 1, sum + (i == 1), flag && i == max_num); //将位数-1、(如果枚举的i是1,那么sum+1,否则不加)、传flag表达式
其实,现在还没完。时间复杂度太高了,原因是我们大量枚举了一些重复的数据。
例如,在我们的dfs返回sum的时候,如果pos、flag 相同的话,那么sum是一样的。
比如N=99999.
我们第一个数枚举的是1,显然,不管后面五个数是什么,我们都不会超过N。
所以,在不受限制的情况下,能得到的1的个数是固定的。
当我们枚举到以2开头的数,发现此时后面五个数仍然不受限制。
这种情况与我们第一位枚举:3、4、5、6、7、8、9 的答案相同。
我们就不需要再去递归后面的数。直接返回一个在这个状态下记录过的答案就好了。
这就是记忆化搜索。
那么加上了记忆化搜索,这道题才算真的完结了。
希望对数位dp有一些了解。
附代码:
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<cmath> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<cctype> #include<map> #include<set> #include<queue> #include<numeric> #include<iomanip> #include<stack> #include<list> using namespace std; typedef long long ll; const int N = 1e6 + 7; ? ll dp[10][200]; int st[10]; ? ll dfs(int pos,int sum,int flag) { ? ? ll ans = 0; ? ? if (pos == 0)return sum; ? ? if (!flag and dp[pos][sum] != 0)return dp[pos][sum]; ? ? int max_num = flag ? st[pos] : 9; ? ? for (int i = 0; i <= max_num; i++) { ans += dfs(pos - 1, sum + (i == 1), flag && i == max_num); } ? ? if(!flag) dp[pos][sum] = ans; return ans; } ? int main() { ? ? ll n; cin >> n; ? ? int digital = log10(n)+1; ? ? ll temp = n; ? ? ll cnt = 0; ? ? while (temp) { st[++cnt]= temp % 10; ? ? ? ? temp /= 10; ? } ? cout<<dfs(digital, 0, 1)<<endl; ? ? } ?
来一道更难一点的吧。
[P2602 ZJOI2010] 数字计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
简单描述一下题目:
给你两个数a,b,让你求出a~b内,数字0~9分别出现了多少次。
先给出dp的定义
ll dp[20][20][2][2][10]; // dp[pos][sum][limit][zero][num] 位数、枚举到当前位数时数字num出现的次数、是否贴合、是否有前导0、我们要寻找的数。
为啥要这样定义,其实后面三个是不需要的,完全可以用二维dp,也就是只要pos,sum。
这两个是必须的,sum在不同的题目里面含义不一样,这是用来区分状态的变量。
在我们的记忆化中非常重要。
然后,对于1~9,上一道题已经给出了求发。
现在,我们要解决0。
求非0的数字,我们通常都忽视前导0的作用,直接在数字前面补上前导0.
但在处理0的时候,我们不能将前导零计入答案。
所以,我们要像设置贴合标记一样,设计一个标记,代表当前状态下是否有前导0。
如果有前导0(zero=1),那么 i==0 时, 不计入sum中
如果有前导0(zero=1),那么 i!=0 时, 不计入sum中
如果无前导0(zero=0),那么i==0时,计入sum中。
如果无前导0(zero=0),那么i!=0时,不计入sum中。
可以得到条件:zero==0 and i==0
左右都满足时,才计入sum中
完成了一半,接下来考虑如何将前导零标记zero 传入下一层。
如果当前有前导零(zero=1),并且 i==0 ,则下一层有前导零
如果当前有前导零(zero=1),并且i!=0,则下一层无前导零
如果当前无前导零(zero=0),并且i==0,则下一层无前导零
如果当前有前导零(zero=1),并且i!=0,则下一层无前导零
对于上面的四种分类,我们发现只有一种情况,前导零会传导下一层,也就是:zero==1 and i==0
否则下一层无前导0
写到这里,基本上就结束了,我们可以分开写两个dfs,一个算0,一个算1~9,然后就可以得到答案
然后就是处理一下记忆化的情况,要想直接返回记忆过的东西,那么必须不能受限制。因为,每个数的限制都不同,但如果不受限制,那么从不受限制开始,后面的答案是相同的。
例如 12_ _ _ , 如果后面三个数的枚举不受限制,那么后面三个数枚举的种类是固定的。
所以记忆化条件就是:!limit and !zero and dp[pos][sum][limit][zero][num]!=-1
但,事情还没有结束,有没有更优雅的代码,因为如果写两个dfs实在是太丑了。
我们可以考虑将两种情况合起来。那么我们就需要注意sum的变化。
对于 0而言, 如果sum要变化,则 需要无前导0并且 i==0 .
对于1~9 而言,如果sum要变化,则 只要i==num就可以。
但是我们不能写:(zero!=1 and i==0 ) and (i==num)
因为,当i非0时,由于前半句有i==0
故前半句必错。
所以,我们需要使得,当i非0时,前半句对后面无影响。 我们可以想到 用 ||
故,我们可以换成 (zero!=1 or i!=0 ) and (i==num)
.
此题,到此结束。完结撒花
#include <iostream> #include<cstring> #include <cmath> using namespace std; typedef long long ll; const int mod = 1e9 + 7; ? ll dp[20][20][2][2][10]; // dp[pos][sum][limit][zero][num] ll st[20]; ? ? ll dfs(int pos, int sum, int limit,int zero,int num) { ll ans = 0; ? if (pos == 0)return sum; ? if (!limit and !zero and dp[pos][sum][limit][zero][num] != -1)return dp[pos][sum][limit][zero][num]; ll max_num = limit ? st[pos] : 9; ? for (int i = 0; i <= max_num; i++) { ans += dfs(pos - 1, sum +( (zero!=1 || i) && (i == num) ), limit&& i == max_num, zero && (i == 0), num ); } ? if (!limit and !zero) dp[pos][sum][limit][zero][num] = ans; return ans; } ? ? ll work(ll p, ll num) { ? memset(dp, -1, sizeof(dp)); ? ll cnt = 0; ? while (p) { st[++cnt] = p % 10; p /= 10; } return dfs(cnt, 0, 1, 1,num); } ? int main() { ll a, b; cin >> a >> b; for (int i = 0; i <= 9; i++) { cout << work(b, i) - work(a - 1, i) << ' '; } } ?
继续来一道和上面差不多的题目:
P4999 烦人的数学作业 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题面意思是:让你求出 a~b之间的所有数位的和。结果对1e9+7取模
显然,这题我们仍可以用到上一题的内容。
先求出a~b 之间 1、2、3、4……9 的个数。然后分别乘以:1、2、3……9即可。
第二种解法:很简洁。
我们说过,定义dp的时候,关键是定义齐全所有状态。
模板就是:
dp[pos][sum][limit][x][x] //前面三个是最常见的状态,后面的话根据题目来设计
那么此时,我们就要考虑这个sum在这里的含义了。
在上一题中,sum 是 num这个数字,在枚举到pos位时,出现的次数。
但这一题,我们并不需要求出现次数,我们要求的是数位和。
那么这里的sum,就可以定义成,在枚举到pos位时,当前状态下的数位和。
很好,这道题结束了。
然后剩下的是一些很细节的东西:
1、尽量不用一些返回值是double 的函数。 例如log10(),pow(),这题的数据下会有精度问题
2、结果要去取模,由于可能出现负数,所以要+模数再取模
#include <iostream> #include<cstring> #include <cmath> using namespace std; typedef long long ll; const int mod = 1e9 + 7; ? ll dp[30][18*9][2]; // dp[pos][sum][limit] ll st[30]; ? ll dfs(int pos, int sum, int limit) { ? ll ans = 0; if (pos == 0)return sum; ? ? if ( dp[pos][sum][limit] != 0)return dp[pos][sum][limit]; ? ll max_num = limit ? st[pos] : 9; ? for (int i = 0; i <= max_num; i++) { ans = (ans + dfs(pos - 1, sum + i, limit && (i == max_num)))%mod; } ? ? if(!limit)dp[pos][sum][limit] = ans; return ans; ? ? } ? ? ll work(ll p) { ? ll tot = 0; ? ? while (p) { st[++tot] = p % 10; p /= 10; } ? ? return dfs(tot, 0, 1) % mod; } ? int main() { ? ? int t; cin >> t; ? ? memset(dp, 0, sizeof(dp)); ? ? while (t--) { ll l, r; cin >> l >> r; cout << (work(r) - work(l - 1)+mod) % mod<<endl; } } ?