E 简洁的数

• 题意：给定区间，求区间内不超过个数位在间的数有多少个
• 区间，将区间转换为求解，但是因为这里，所以这样转换不太方便。注意到判断单个数是否合法比较容易，就可以转换为，并且单独判定是否合法。
• 对于判定区间中有多少合法的数，我们去从高到低去枚举数位，并判定合法情况计数
  • 将按数位从低到高分解，并且存入中，其中代表第位的数位，代表第位时，有个非的数的数字的个数
  • 从高到低去枚举数位，设当前枚举的位为，为了确保枚举的数小于，我们需要知道枚举的位上的数字是否等于，若不等于，则位的数可以取，否则取
  • 对于没有任何限制的数，我们将其记忆化使用。反之直接枚举

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
int dp[30][5], num[30];//记忆化，存储数位
//num[i]代表数字的第i位

int dfs(int now, int lim, int cnt) {//从高到低位枚举
    if(cnt > 3) return 0;//合法性判断
    if(!now) return 1;//此数合法
    if(!lim && dp[now][cnt]) return dp[now][cnt];
    int Ceil = lim ? num[now] : 9;//确定上界
    int ans = 0;
    for(int i = 0; i <= Ceil; ++i) {
        ans += dfs(now - 1, lim && (i == num[now]), cnt + (i != 0));
    }if(!lim) dp[now][cnt] = ans;//记忆化
    return ans;
}

int solve(string x) {
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= x.size(); ++i) num[i] = x[x.size() - i] - '0';
    return dfs(x.size(), 1, 0);
}

signed main() {
    string a, b;
    while(cin >> a >> b) {
        int flag = 1, cnt = 0;
        for(int i = 0; i < a.size(); ++i) {
            if(a[i] != '0') ++cnt;
            if(cnt > 3) flag = 0;
        }//单独判定a是否可行
        cout << solve(b) - solve(a) + flag << endl;
    }
    return 0;
}