Loading... >数位dp基本模型，给定闭区间$[l,r]$，求这个闭区间中满足题目要求的数的个数。 <!--more--> 我们可以从数字的每一位来枚举，从高位向低位枚举，我们可以用 dp[i][j] 来表示枚举到 i 位时，数字为 j 时的方案数（答案数）。但是我们需要考虑一些限制我们决策的条件，假设我们要求小于等于 243 的数字中符合条件的有几个： 1. 当我们第一项为 1 时，我们后面一位可以枚举 0∼9 2. 当我们第一项为 2 时，我们后面一项就只能枚举 0∼4 可见我们需要通过判断前一项来决定后一项最高可以取值的大小。同时我们也需要考虑一些数字前面一直是 0，并且会影响答案的情况（例如统计各个数字出现的次数）。以下是模板： ```cpp #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数](https://www.luogu.org/problem/P2657) - 题意：给定一个区间$[l,r]$，求其中满足条件 不含前导$0$且相邻两个数字相差至少为$2$的数字个数。 - 按照模板写就行了 ```cpp #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; } ``` ### [杠杆数](https://www.luogu.org/problem/P1831) - 我看到这道题的时候通过数据范围判断它应该是数位dp，但是我不知道以哪一位为支点计算那些怎么做，也是因为这道题才学的数位dp。 - 发现正常的模板搜索第二个变量保存了上一个数是几，但是这个题不能这么算，所以就对于一个1道n的统计，枚举一下支点，然后记录一下支点位置和到当前的和，额。。。我不知道自己说了什么，看注释吧。 ```cpp #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; } ``` Last modification：March 8, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏