动态规划-数位DP 其他

【动态规划-数位DP】一些题目有这样的规律：求一段区间内xx的个数是多少。xx描述了要求的数具有的性质。假设求[l, r]这个区间，可以处理成求dp(r) - dp(l - 1)。
例：科协里最近很流行数字游戏。某人命名了一种不降数，这种数字必须满足从左到右各位数字成小于等于的关系，如 123，446。现在大家决定玩一个游戏，指定一个整数闭区间 [a,b]，问这个区间内有多少个不降数。现在假设一个n位数为N，我们求1~N之间的不降数数量。
将N按数位从高到低拆开。
可以使用vector来存while (n) nums.push_back(n % 10), n /= 10;

文章图片

我们有有计划地枚举0~N的所有数。在最高位时，两种划分方式，一是填0 ~a n ? 1 ? 1 a_{n-1}-1 an?1??1，后面的数位上的数就可以没有限制地填了；另一种是填 a n ? 1 a_{n-1} an?1?，这时候就要看第2高位如何填，也是两种划分方式，0 ~a n ? 2 ? 1 a_{n-2}-1 an?2??1， a n ? 2 a_{n-2} an?2?。以此类推…

文章图片

目前的状态已经被划分成了：
1，最高位填0~2，后面随便填的所有方案。
2，最高位填3，且次高位填0~3，后面随便填的所有方案。
3，最高位填3，且次高位填4，第三位填0~4，后面随便填的所有方案
4，最高位填3，且次高位填4，第三位填5，第四位填0~5，后面随便填的所有方案
5，最高位填3，且次高位填4，第三位填5，第四位填6，第五位填0~6的所有方案。
6，最高位填3，且次高位填4，第三位填5，第四位填6，第五位填7的方案。即填N。
注意：由于N比较特殊，是一个不降数，所以我们能枚举出所有方案。当N=34543时，我们枚举不到第四位填4的情况。为了简便计算，我们要预处理一个数组f[i, j]，表示位数为 i ，且最高位上是 j 的合法方案数

void init() { for (int i = 0; i <= 9; i ++ ) f[1][i] = 1; for (int i = 2; i < N; i ++ ) for (int j = 0; j <= 9; j ++ ) for (int k = j; k <= 9; k ++ ) f[i][j] += f[i - 1][k]; }

最终代码：

#include #include #include #include using namespace std; const int N = 35; int l, r; int f[N][N]; void init() { for (int i = 0; i <= 9; i ++ ) f[1][i] = 1; for (int i = 2; i < N; i ++ ) for (int j = 0; j <= 9; j ++ ) for (int k = j; k <= 9; k ++ ) f[i][j] += f[i - 1][k]; }int dp(int n) { if (!n) return 1; vector nums; while (n) nums.push_back(n % 10), n /= 10; int res = 0; int last = 0; for (int i = nums.size() - 1; i >= 0; i -- ) { int x = nums[i]; for (int j = last; j < x; j ++ ) res += f[i + 1][j]; if (x < last) break; last = x; if (!i) res ++ ; }return res; }int main() { init(); while (cin >> l >> r) cout << dp(r) - dp(l - 1) << endl; return 0; }