数字游戏 - 计数 DP
z_h_x
·
·
个人记录
题意
定义 不降数 为某数字各个数位上的数从高位到低位均为非降。指定一个整数区间 [a,b]，求这个区间内有多少不降数。
## 思路
题意十分清晰，暴力显然不允许。
这道题需要用到 **计数 DP** 来解决。
所谓的 **计数 DP**，是指在一段区间内 DP 以统计某种符合条件的数的问题。执行计数 DP 时一般先把区间划分成几个部分，通过初始化使一些特殊部分得到求解，再从这些转移出其他的状态。
这道题求的是不降数。通常计数 DP 的状态定义为 $f_{n,n}$，$n$ 为最大的位数。$f_{i,j}$ 表示如果这个数是 $i$ 位数，最高位为 $j$，到这个数共有多少满足的数。
先来看初始化。只有 $1$ 位的数自然是不降数。其他位枚举 $i,j$，每次枚举到从 $i-1$ 转移。很显然，**$j$ 以下的数一旦加入，构成的数就不是不降数了**。所以加入的数必须是 $\ge j$ 的。直接从 $j$ 枚举 $k$ 即可。
初始化的状态转移方程就是：
$$
\left\{\begin{matrix}f_{1,i}=1\\f_{i,j}=\sum_{k=j}^{10} f_{i-1,k}\end{matrix}\right.
$$
还需要有一个能求出 $[0,x]$ 区间内有多少个不降数的函数 $calc$。把 $x$ 的各个数位分离，放入一个数组内。统计两个变量 $res$ 和 $last$，分别表示答案和上一位是几（动态维护 $last$）。从高到低遍历数位，第二维从 $last$ 开始一直遍历到 $a_i$ 结束，用 $res$ 加上区间内的不降数数量，实时修改 $last$ 变量，最后返回 $res$ 即可。
最后类似于求前缀和，答案是 $calc(r) - calc(l-1)$。
**Code**
```c++
#include<bits/stdc++.h>
using namespace std;
#define TRACE 1
#define tcout TRACE && cout
#define int long long
#define endl '\n'
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int N = 12, M = 2e6+10;
const int INF = 0x3f3f3f3f3f3f3f3f;
//预处理
//0000-0999
//...
int f[N][N]; //如果这个是 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 < 10; j ++){
for(int k = j; k < 10; k ++){
f[i][j] += f[i-1][k];
}
}
}
}
int calc(int x){ //0~x间有多少个
if(x == 0) return 1;
int a[N] = {0};
int n = 0;
while(x){
a[++n] = x % 10;
x /= 10;
}
int res = 0;
int last = 0; //上一位是几
for(int i = n; i >= 1; i --){
if(a[i] < last) break;
for(int j = last; j < a[i]; j ++){
res += f[i][j];
}
last = a[i];
if(i == 1) res++;
}
return res;
}
signed main(){
init();
int l, r;
while(cin >> l >> r){
cout << calc(r) - calc(l-1) << endl;
}
return 0;
}
```