数位DP 学习笔记

数位dp基本模型,给定闭区间$[l,r]$,求这个闭区间中满足题目要求的数的个数。

我们可以从数字的每一位来枚举,从高位向低位枚举,我们可以用 dp[i][j] 来表示枚举到 i 位时,数字为 j 时的方案数(答案数)。但是我们需要考虑一些限制我们决策的条件,假设我们要求小于等于 243 的数字中符合条件的有几个:

  1. 当我们第一项为 1 时,我们后面一位可以枚举 0∼9
  2. 当我们第一项为 2 时,我们后面一项就只能枚举 0∼4

可见我们需要通过判断前一项来决定后一项最高可以取值的大小。同时我们也需要考虑一些数字前面一直是 0,并且会影响答案的情况(例如统计各个数字出现的次数)。以下是模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
#define N 20
int dp[N][N], a[N], n, m;
// 数位 dp 是需要深搜的,`dp` 数组只是做记忆化搜索用
int dfs(int pos, int pre, bool limit, bool frontzero) {
// `frontzero`: 前导 0 的判断
// `pre`: `pos` 前一位的数字
if (pos == 0) return 1; // 枚举完毕,退出
if (!frontzero && !limit && dp[pos][pre] != -1) return dp[pos][pre];
// 返回 `dp[pos][pre]` 的条件:前导非零 且 无上限限制 且 `dp` 数组的这一位有值
// 注意这里必须把 `!frontzero` 和 `!limit` 写在前面 来防止 `dp` 数组越界
// 因为后面需要在前导零的时候做一点操作
int p, ret = 0;
int up = limit ? a[pos] : 9;
for (int i = 0; i <= up; ++i) {
if () continue;
// 当枚举到的这一位不符合条件时就忽略,继续枚举
p = i;
if (frontzero && i == 0) p = -INF;
// 这里 `-INF` 只是一个前导 0 的标记,数值并没有太大意义。
ret += dfs(pos - 1, p, limit & (i == up), (p == -INF));
// 这里 `p = -INF` 时也是会传进函数作为 `pre` 参数的,
// 所以前面要把 `frontzero` 写前面
}
if (!frontzero && !limit) f[pos][pre] = ret;
return ret;
}

int solve(int x) {
// `solve(x)`: 处理不大于 `x` 的数的答案
int idx = 0;
while (x) {
a[++idx] = x % 10;
x /= 10;
} // 预处理 `x` 的每一位
memset(dp, -1, sizeof(dp));
return dfs(idx, -INF, 1, 1);
// 注意初始化
}

int main() {
cin >> n >> m;
cout << (solve(m) - solve(n - 1));
return 0;
}

windy数

  • 题意:给定一个区间$[l,r]$,求其中满足条件 不含前导$0$且相邻两个数字相差至少为$2$的数字个数。
  • 按照模板写就行了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

int dp[15][15], a[15];

int dfs(int pos, int pre, bool limit, bool frontzero){
if(pos == 0) return 1;
if(!limit && !frontzero && dp[pos][pre] != -1) return dp[pos][pre];
int ret = 0;
int up = (limit ? a[pos] : 9);
for(int i = 0; i <= up; i++){
if(abs(i - pre) < 2) continue;
int p = i;
if(frontzero && i == 0) p = -INF;
ret += dfs(pos - 1, p, limit & (i == up), (p == -INF));
}
if(!frontzero && !limit) dp[pos][pre] = ret;
return ret;
}

int solve(int x){
int idx = 0;
while(x){
a[++idx] = x % 10;
x /= 10;
}
memset(dp, -1, sizeof(dp));
return dfs(idx, -INF, 1, 1);
}

int main(){
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", solve(b) - solve(a - 1));
return 0;
}

杠杆数

  • 我看到这道题的时候通过数据范围判断它应该是数位dp,但是我不知道以哪一位为支点计算那些怎么做,也是因为这道题才学的数位dp。
  • 发现正常的模板搜索第二个变量保存了上一个数是几,但是这个题不能这么算,所以就对于一个1道n的统计,枚举一下支点,然后记录一下支点位置和到当前的和,额。。。我不知道自己说了什么,看注释吧。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dp[20][20][3009], a[20];

ll dfs(int pos, int x, ll s, bool limit, bool frontzero){
if(pos == 0) return (!frontzero && s == 0);
//然后返回1的条件就是和为0(满足平衡)
//并且不能是0.
if(!limit && !frontzero && dp[x][pos][s] != -1) return dp[x][pos][s];
int up = (limit ? a[pos] : 9);
ll ret = 0;
for(int i = 0; i <= up; i++){
ret += dfs(pos-1, x, s+(1ll*i*(pos-x)), limit & (i == up), frontzero&(i==0));
//这里就是转移。。。
}
if(!limit && !frontzero) dp[x][pos][s] = ret;
return ret;
}

ll solve(ll x){
int idx = 0;
while(x){
a[++idx] = x % 10;
x /= 10;
}
memset(dp, -1, sizeof(dp));
ll ans = 0;
//就这个地方,枚举一下支点位置。
for(int i = 1; i <= idx; i++){
ans += dfs(idx, i, 0ll, 1, 1);
}
return ans;
}

int main(){
ll a, b;
scanf("%lld%lld", &a, &b);
printf("%lld", solve(b) - solve(a - 1));
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×