1.基础
1.1. 问题
数位 DP 解决的一般都是和数字相关的计数问题,常见的有 \(l \sim r\) 中有多少数符合某个关于数位的条件。
对于这种问题,我们都是先用前缀和转化成小于等于某个数的问题。
下面以 P2602 [ZJOI2010] 数字计数 为模板题。
1.2 记忆化搜索
我们先枚举每个数码。
我们考虑设一个状态 \((i,j,0/1,0/1)\) 表示当前处理到了第 \(i\) 位,已经填了 \(j\) 个当前数码,有无前导 \(0\),是否贴着上界。
我们发现,有前导 0 或者贴着上界的状态其实只会搜索到 1 次,所以我们只用记录 \(f(i,j)\) 表示 \((i,j,0,0)\) 状态的答案来进行记忆化搜素。
首先,如果 \(i = 0\),我们直接返回 \(j\)。
其次,如果已经计算过了,我们返回答案。
否则,我们根据是否贴着上界算一下这一位的范围,然后枚举每个数码。
枚举的过程中,我们需要特判 0 和前导 0 的情况。
得出答案后在记忆化并返回即可。
时间复杂度是位数乘以进制。
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;
int tmp, num[N] = {0};//表示当前处理的数字
long long f[N][N] = {{0}};//f[i][j] 表示处理到 i 已经有了 j 个 tmp,且没有前导 0 和最高位限制
long long dfs(int pos, int sum, bool hd, bool lim) {
long long ans = 0ll;
if (pos == 0)
return sum;
if (!hd && !lim && f[pos][sum] != -1)
return f[pos][sum];
int up = (lim ? num[pos] : 9);
for (int i = 0; i <= up; i++) {
if (i == 0 && hd)
ans += dfs(pos - 1, sum, hd, lim && i == up);
else if (i == tmp)
ans += dfs(pos - 1, sum + 1, false, lim && i == up);
else
ans += dfs(pos - 1, sum, false, lim && i == up);
}
if (!hd && !lim)
f[pos][sum] = ans;
return ans;
}
long long slv(long long n) {
int len = 0;
while (n > 0)
num[++len] = n % 10, n /= 10;
memset(f, -1, sizeof f);
return dfs(len, 0, true, true);
}
int main() {
long long l, r;
cin >> l >> r;
for (int i = 0; i <= 9; i++) {
tmp = i;
cout << slv(r) - slv(l - 1) << " ";
}
return 0;
}
1.3 适合多测的方法
我们从另一个角度看,每次我们相当于需要处理的就是一个数划分成的若干区间。关键就是上界。
所以我们可以直接最开始计算 \(f(i,j)\) 表示从低到高确定了 \(i\) 位,\(j\) 的总个数。
然后对于一个数,我们从高到低处理,枚举每一位用 dp 值计算出答案即可。
这样我们只用一遍 dp 就可以解决问题了。
标签:int,sum,pos,long,小记,include,我们,DP,数位
From: https://www.cnblogs.com/rlc202204/p/18389257