CF1036C Classy Numbers 题解 数位DP

题目链接：https://codeforces.com/problemset/problem/1036/C

题目大意：求区间 ([L,R]) 范围内非零数字位数不超过 (3) 个的数字个数。

解题思路：数位DP。(f[p][num]) 表示到第 (p) 位为止有 (num) 个非零数字的数的个数。

示例代码：

#include <bits/stdc++.h>
using namespace std;
long long f[20][4], a[20];
bool vis[20][4];
long long dfs(int p, int num, bool limit) {
    if (num > 3) return 0;
    if (p < 0) return 1;
    if (!limit && vis[p][num]) return f[p][num];
    if (!limit) vis[p][num] = true;
    int up = limit ? a[p] : 9;
    long long ans = 0;
    for (int i = 0; i <= up; i ++) {
        ans += dfs(p-1, num + (i!=0), limit && i==up);
    }
    if (!limit) f[p][num] = ans;
    return ans;
}
long long handle(long long num) {
    int p = 0;
    while (num) {
        a[p++] = num % 10;
        num /= 10;
    }
    return dfs(p-1, 0, true);
}
int T;
long long L, R;
int main() {
    scanf("%d", &T);
    while (T --) {
        scanf("%lld%lld", &L, &R);
        printf("%lld
", handle(R) - handle(L-1));
    }
    return 0;
}